I have a dual boot Windows xp/Ubuntu set up on this PC.

However, I'm using an ATI Radeon HD 4830 with HDMI to an HDTV.

I have video, but no sound, I have all of my sound output set to HDMI under system preferences, but it still doesn't play any sounds.

I updated all of the proprietary drivers, and set up the catalyst control center for the video card, too.

I have no idea wtf the issue is.

I run Mandriva on my laptop, so i'm not really sure how things work with Ubuntu, but when I needed to find drivers for my video card, I had to use the backports repository

Well, the proprietary drivers should in theory enact the HDMI.

I don't know what the problem is, however, I really don't think it's drivers.

Do you have sound working through non HDMI?

Right click your speaker icon and open the volume control panel. Make sure the master volume is all the way up.

For some reason this is defaulted to mute for some people when installing 9.04.

Could this be a DRM issue? I know there are some with HDMI.

Yeah, master volume is up, and not muted.
A buddy of mine worked on it remotely, and the sound worked until i rebooted, so I know it can work, but I have no clue what he did. :P

OK, make sure you're using ALSA as the mixer and that Surround is selected.

Yep, done and done.

Strange thing is, when I try to test the playback devices in the sound preferences menu, I get an error stating that the device is already in use.

Try using Synaptic and removing all Pulse Audio related packages and then getting the latest versions.