I've actually rewritten Anders mindstorms NXT bluetooth C++ library
(and fixed a load of bugs, updated the code to include the newer colour sensor, added xbox 360 joypad support, and added the ability to write 24bit images). Everything works without a hitch on linux, and so it should be *relatively* straight forward to get running on the Pi. I've only just received conformation that my Pi order is being processed, so I should get one within the next week or two. Rest assured, putting together a Pi version of the lib is high on my agenda
I wouldn't bother with the linux port found on Anders webpage, there are more bugs in the bluetooth code than I can remember.
You'll need a bluetooth dongle (there is next to no information on the USB protocol used by the NXT).
The C++ code depends on the joystick and bluetooth libraries, so assuming they're available, and you've got bluetooth up and running, it should be childs play to compile it for the Pi....
I'll bookmark this thread and report back once my Pi turns up (hopefully within the next 2 weeks)