I finally had some time to do a little experimenting with this today, and I think I can now cast some light on the puzzling differences that people are experiencing.

If I do the following:
disconnect wlan
run xterm
sudo gainroot
ifconfig wlan0 down hw ether 00:00:00:00:00:00 (<- any real MAC address)
ifconfig wlan0 up

my MAC address appears to have changed. But as most other people report, if I attempt to reconnect to my router, I can only get "Network connection error".

However I noticed another unsecured wlan nearby, so I tried connecting to that, and guess what? No problem!

So I temporarily disabled security on my own router and tried to connect to it again. Presto, no problem connecting, and the Attached Devices report correctly shows my altered MAC address for the N800.

So the problem appears to be that for some reason the N800 wlan stack is unable to deal with WEP/WPA security after the MAC address is altered. Speculating that there's some wrong information hanging around in memory somewhere, I tried various experiments (like deleting the saved information for my normal connection, booting the N800 in offline mode, then doing the MAC address change and connecting to the router as a completely fresh connection), but no luck.

So, changing MAC address does work partly, but apparently not for my purpose of connecting to the secured network at work.