I've got the same setup with the same ISP. Last thing at night I shutdown Vista then switch off everything at the wall. (all the kit including the livebox is on a surge protector strip).
In the morning I switch the strip back on, hit the tit on the PC, and by the time Vista boot completes, the router is normally just finishing its power-on cycle and the "Internet" LED is on. Windows mail is part of my auto-startup, and it's a toss-up which is ready first. Some mornings I get "couldn't connect" error messages and have to click "send/receive" again to download my email. Some mornings the livebox gets ready first and the mail is there waiting.
If I ever have to boot during the day, when the livebox is already connected, Vista and XP connect immediately.
My second PC connects XP wirelessly and again there is no delay, though it did take me a while to figure out what I'd not done correctly, as I originally had to manually start the wireless connection every boot - now by time XP boot is finished, AVG is already downloading its daily updates.
What do you mean by Vista won't connect ? What indications do you get ? My only connection problem is as described above, where Vista is too quick for the livebox on first power up. At all other times, startup tasks which require the internet (like AVG and my Met Office sidebar gadget) instantly connect.