A shortcut in the Start menu didn't work for me but this did:
In case that link goes bad:
Control Panel->Administrative Tools->Schedule Tasks
Create basic task... -> When I logon -> Start a program: "c:\Windows\System32\rasphone.exe" arguments: "-d NetworkConnection" where NetworkConnection is replaced by the name of your network connection.
If you don't know the name, run "rasphone" from the Start button and look at the list. You must put the name in quotes if there's a space in it. To test if it works, you can test it from the command-line.
You should also configure the connection to not require name and password when connecting so that it'll connect when you're away from the computer. To do that, first configure the connection to require name/password. Next disconnect and reconnect. In the connect screen, enter name and password and check the "remember password" option, for everyone. Now connect and that will save the "remember password" option. Finally, go back to the properties and remove the "require name/password" option.