The only time I've had prob's with kmail, has been when I've incorrectly typed in the config for one of the mail addresses, usually a typo like smpt instead of smtp
If you have dual boot, you could try double checking stuff like that with windows, just to make sure that you've got the incoming server address correct.
Because I'm thinking along the lines of, that if you can get net access, it could possibly be a "setting's" problem.
Maybe this help's? maybe not (but it's the only thing that I can think of)