Se qualquer outro aplicativo puder se conectar à Internet e o Ubuntu Software Center não puder, então definitivamente algo está errado. Relate este bug, mesmo que o bug esteja em outro lugar (por exemplo: no wvdial, ou em algumas configurações de rede do sistema), os desenvolvedores irão ajudá-lo a diagnosticar esse problema e determinar o motivo. A página em que você deve reportar bugs no Ubuntu Software Center é: link