Further results. Sat outside OfficeDepot and tried to connect to their free WiFi hotspot. Always got the 'link-local ip address' and the ip address claims to be 169.254.63.223 (nowhere near what it should be). At that time there were three other open AP, plus two other 'locked'. Same results connecting to the other two open AP (coffee shop and 'KiteNetFree') - no success, could not browse.
Later outside BestBuy, tried to connect to KiteNetFree again and it worked normally. Browse/email send/receive OK. Tried to connect to BestBuy and it failed (despite being open). Only two APs were visible at that moment - BestBuy and KiteNetFree.
So it appears that the results indicate the more APs visible, the harder it is to get an IP address, even though it 'Connects' fine and the signal is good (2 out of 4 bars). Anyone else with similar experiences on the N800? Remember at home it works flawlessley to my WEP-enabled router, never having failed to connect EVER (even though I can see 4 open APs, 3 locked APs)

This has to be a bug in the N800! It should not be this difficult to connect to free WiFi hotspots, and IMHO makes the N800 useless, at best unreliable.