Under Windows XP:
1) Control Panel -> Network Connections
2) Find your connection. This is NOT your ethernet adapter.
3) Right click on the icon and select "Properties"
4) Uncheck "Prompt for name and password..." and Click OK
5) Create a shortcut in your startup folder. In your post you stated you already did this. Make sure you delete the old shortcut first.
The above instruction will only work if you are using XP's built-in client.
Check the Startup folder