KMail output suggests to me it might have to do with KMail failing to communicate with NetworkManager and thus determine whether you are online.
Do you use NetworkManager for managing network connections? If yes, does the daemon run fine?
I could also suggest the not-so-probable scenario that this might be a DBUS issue. Is a DBus session active?
-- Mavridis Philippe