Is your firewall blocking Warband? Check that, and unblock it if it is. If you can surf the web to ask for help about it, I doubt it's your connection, though I'd check to make sure everything is secure anyway.
Joseph!
Make sure you've bought the game(ie not still trying to get on using the beta.exe) and updated to the latest patch.
Other than that, try another server. Sometimes I get that error if I haven't played on the server in a while. Tends to reset though after getting on a server and then off.