Eu tenho o mesmo problema, também em 13.04 - 64 bits. No Ubuntu 12.10 - 64 bits, na mesma máquina, funcionou.
De qualquer forma, até que o problema seja resolvido, você pode editar manualmente seu arquivo conf para alterar os parâmetros do proxy para o Synaptic.
O arquivo é /root/.synaptic/synaptic.conf
e você pode especificar o usuário e a senha no httpProxyUser
e
httpProxyPass
linhas