Also happens with telepathy-haze (Yahoo).

After killing telepathy-haze, the Yahoo account works again.

Note before killing telepathy-haze.. changing the username works to connect to another YM account, but when I changed the username back to the problematic username, it gives "Disconnected - Network Error" again immediately (without any sign of progress of actually trying to connect to the network).

$ aptitude show empathy telepathy-haze 

Package: empathy                         
State: installed
Automatically installed: no
Version: 2.32.1-0ubuntu1
Priority: optional
Section: gnome
Maintainer: Ubuntu Core Developers <email address hidden>
Uncompressed Size: 2.458k
Depends: libatk1.0-0 (>= 1.29.3), libc6 (>= 2.7), libcairo2 (>= 1.2.4),
         libcanberra-gtk0 (>= 0.4), libcanberra0 (>= 0.2), libdbus-1-3 (>=
         1.0.2), libdbus-glib-1-2 (>= 0.78), libdbusmenu-glib1 (>= 0.3.12),
         libebook1.2-9 (>= 2.30.3), libedataserver1.2-13 (>= 2.30.3),
         libenchant1c2a (>= 1.6), libfolks-telepathy0 (>= 0.1.9), libfolks0 (>=
         0.1.15), libfontconfig1 (>= 2.8.0), libfreetype6 (>= 2.2.1),
         libgconf2-4 (>= 2.31.1), libgcr0 (>= 2.26.0), libgdk-pixbuf2.0-0 (>=
         2.21.6), libgee2 (>= 0.5.2), libglib2.0-0 (>= 2.25.16),
         libgnome-keyring0 (>= 2.26.0), libgnutls26 (>= 2.7.14-0), libgp11-0 (>=
         2.24), libgstfarsight0.10-0 (>= 0.0.1), libgstreamer-plugins-base0.10-0
         (>= 0.10.0), libgstreamer0.10-0 (>= 0.10.4), libgtk2.0-0 (>= 2.21.8),
         libindicate-gtk2 (>= 0.2.2), libindicate4 (>= 0.3.3),
         liblaunchpad-integration1 (>= 0.1.17), libnm-glib2 (>=
         0.8~a~git.20090826t185111.79489be), libnotify1 (>= 0.5.0),
         libnotify1-gtk2.10, libpango1.0-0 (>= 1.18.0), libpng12-0 (>=
         1.2.13-4), libsoup2.4-1 (>= 2.4.0), libtasn1-3 (>= 1.6-0),
         libtelepathy-farsight0 (>= 0.0.6), libtelepathy-glib0 (>= 0.11.15),
         libtelepathy-logger1 (>= 0.1.2), libunique-1.0-0 (>= 1.0.0),
         libwebkit-1.0-2 (>= 1.1.15), libx11-6, libxml2 (>= 2.7.4), zlib1g (>=
         1:1.1.4), empathy-common (= 2.32.1-0ubuntu1),
         telepathy-mission-control-5, gnome-icon-theme (>= 2.30.0), dbus-x11,
         telepathy-logger
Recommends: telepathy-gabble, telepathy-salut, libdconf0, gvfs-backends,
            telepathy-haze, telepathy-butterfly, nautilus-sendto-empathy
Suggests: telepathy-idle, vino
Breaks: telepathy-butterfly (< 0.5.10)
Replaces: libempathy-gtk-common
Description: GNOME multi-protocol chat and call client
 Instant messaging program supporting text, voice, video, file transfers and
 inter-application communication over many different protocols, including: AIM,
 MSN, Google Talk (Jabber/XMPP), Facebook, Yahoo!, Salut, Gadu-Gadu, Groupwise,
 ICQ and QQ. 
 
 This package contains the Empathy IM application and account manager.
Homepage: http://live.gnome.org/Empathy

Package: telepathy-haze
State: installed
Automatically installed: no
Version: 0.4.0-1ubuntu0.1
Priority: optional
Section: net
Maintainer: Ubuntu Developers <email address hidden>
Uncompressed Size: 229k
Depends: libc6 (>= 2.4), libdbus-1-3 (>= 1.0.2), libdbus-glib-1-2 (>= 0.88),
         libglib2.0-0 (>= 2.24.0), libpurple0 (>= 1:2.7.0), libtelepathy-glib0
         (>= 0.11.13)
Provides: telepathy-connection-manager
Description: A telepathy connection manager that use libpurple
 Haze is a telepathy connection manager based on libpurple. This allow telepathy
 based application to connect all protocols supported by libpurple (pidgin).