I am having the same issue with my NXT not being able to see my PC. However, there is a work-around. You can pair your NXT with your PC by first searching for the NXT and adding it to paired devices. When asked for a number use 1234 and you will be able to send programs to the NXT.
When i was using the original Lego firmware they could pair fine, but with Lejos 0.4.0 there is no joy so i think we can assume this is a bug with Lejos.
An interesting point to note though, is that even with the NXT and the PC 'paired' the NXT will still not be able to open a connection to your PC.
I am using the default bluetooth stack that was installed with WinXP SP2 not the Widcomm Stack.