I have the exactly the same connectivity problem with the Belkin wireless router. The PC connects to the internet every time when the ethernet cable is attached directly to the cable modem, but via the router, requires multiple restarts before a connection can be established. So far I have tried 2 different routers and 2 different PC's (the first running Vista 64 and the second a wireless laptop running XP 32 bit). I have also reinstalled the latest Belkin software and firmware, but no difference. The Belkin Vision router has a graphic display showing connections, and always shows the PC to be connected when first switched on, but losing the connection as Windows itself boots up.
Any advice would be welcome. Thanks, Ted.