Hm... This is a puzzling one. I would try the following:
Create a new location under Network Preferences.
Reset the PRAM and SMC (to reset the SMC, turn off the machine, then press and hold the power button. Keep holding till the light flashes quickly and the machine will turn on).
Perform the aforementioned bluetooth trick.
If none of those work then I would also try removing the System Configuration folder in /Library/Preferences.
This will cause your system to forget...