Windows was unable to connect to...

All of a sudden, I've got a very annoying problem where Windows no longer wants to connect to my wireless router via WiFi - UNLESS I change the router's encryption setting after each reboot.

I attempt to connect to my router's hotspot and an error message says "Windows was unable to connect to [router's name]". If I change the router's encryption from WEP to WPA then it's fine, but then when I next restart my computer it won't connect until I move it from WPA to WEP. Very annoying as I need to keep going between the two, which really annoys my housemates!

Can anyone help? How would I clear the cache for wireless settings so windows thinks my hotspot is brand new? I've already tried removing my saved connection settings from 'manage wireless networks' but that makes no difference.

Normally, with a post such as this, my first recommendation would be to insure that your wireless adapter drivers are as current and up to date as possible. Additionally, likewise with the firmware on the router. Standard, boiler plate, first things to look at and confirm that they are the most recent.
But; since your post starts with the dreaded four words "All of a sudden", I would actually first recommend a system restore, to a restore point, prior to "all of a sudden" (actual time and or date the problem first appeared.) If that doesn't help, then you might want to try forceably rolling back the driver for the wireless card in device manager.
If still no joy, then just to confirm the excellent trouble shooting you've done to this point, run your router open temporarily and make sure that your connection survives multiple reboots just to validate your suspicions concerning the encryption being the issue. Then if possible move your encryption level to WPA2, with PSK using AES instead of TKIP and see if the connection survives a reboot.