I got tired of replugging my headset between a desktop and Android when someone calls me. Is there a way to stream sound from Ubuntu (I use Pulseaudio) to Android phone over wifi or usb?
Ubuntu has built Ubuntu One Mobile for that very purpose. The service is free to try for one month, then $3.99/month (or $39.99 yearly). It's worth mentioning that the paid account gives you 25GB of storage and unlimited streaming for devices running Android 2.1+, iOS 3.1+ as well as Windows XP, Vista and 7 (and there are rates for additional storage).
(For those who do not wish to stream music, Ubuntu One provides 5GB of cloud storage for free.)
Yes! There is an app called Remote Audio which tunnels your computer's audio output over either SSH or 1 or 2 other protocols. I just installed it and haven't set it up yet, but I plan on using it alongside a remote VNC connection to my desktop at home so I can use Energy XT remotely to sequence song ideas from wherever in the world I happen to be. =)
I'm sure the Ubuntu thing works awesome for music, and probably involves a simpler set-up, but this will stream ANY sound your computer makes, and it's free (and works with any *nix system). The Rhythembox thing you posted about would work awesome too, but you need to set up an Icecast media streaming server first.
Have you thought of an UPnP AV approach? The protocol allows streaming of media between various devices in the same network (e.g. Wifi). There is a large variety of servers and clients for all the OSes.
For example, MediaTomb is a well-known media server also available for Ubuntu. For playback on the phone you could use allShare, which comes preinstalled on some phones, or a free client like BubbleUPNP or Skifta.
You can install airbubble on your android, which works as a speaker using apple's AirPlay (DAAP) protocol.
Pulseaudio can be configured to stream to any AirPlay receiver - check this answer for details on setting that up: https://superuser.com/questions/331126/how-can-you-stream-music-from-ubuntu-to-airplay-speakers-on-your-network-with-ub
With airbubble running, it should show up as a speaker option in the ubuntu sound menu.