Now that VLC (1.1.0) doesn't come with the huge Internet radio list it used to, we must search for alternatives. I've tested a few and TunaPie seems the best I've tried so far. It is compatible with the Icecast directory as well as the Shoutcast (winamp) stream directory service. Further more, Tunapie can even play TV streams and also allows you to record both audio and video streams using streamripper.
You can even use it with your favourite audio/video player. To set this (it's a must if you don't have Xmms installed), once you install Tunapie, go to File > Preferences and under Video and Audio player, enter the player you want. For example, I've entered: "vlc" for both.
Tunapie is available in the official Ubuntu repositories. Install it by searching for Tunapie in the Ubuntu Software Center or use the following command:
sudo apt-get install tunapie