Eu mesmo descobri. Algo não foi instalado por padrão para o Bluetooth. Então, eu instalei o Synaptic novamente e instalei os seguintes pacotes:
sudo apt-get install \
bluetooth blueman \
bluez-hcidump bluewho python-bluez bluez-tools \
brcm-patchram-plus-nexus7
Uma dessas correções meu problema Bluetooth, e agora funciona bem em ambos os sentidos (PC para telefone, telefone para PC). Esqueci de mencionar que o problema ocorre imediatamente após uma nova instalação do Ubuntu 13.04.
Foi uma estupidez da minha parte não ter testado o Bluetooth antes de uma instalação limpa, mas agora está tudo bem.
( Anteriormente na questão declarada como uma solução, isso ajudará futuros usuários mais facilmente. )