This solved the problem for me:
Disable the accounts in Empathy (F4).
Go to seahorse (applications > accessories).
Select the password tab > remove the passwords for the accounts in question.
Enable the accounts back and re-enter the password in Empathy (F4)
The "network error" in my case was not a connection error (the accounts where working in my other jabber client "Psi") but a glitch in seahorse. Empathy relies on seahorse to store the account passwords.