Are you using Nvidia's proprietary driver? I doubt that you will be able to get HDMI working unless you install the proprietary drivers.
Getting them installed can be a little tricky, but the first step is to head on over to Nvidia's driver download page and enter the appropriate information:

For example, if you are using the 32-bit version of Ubuntu, you would select "Linux 32-bit" and download this driver.
Once the download is complete, open a terminal in your downloads directory and run:
chmod 755 name_of_downloaded_file
...to make the file executable and then:
sudo ./name_of_downloaded_file
...to launch the installer.
Update: I totally forgot to write the instructions for actually enabling HDMI output. Run the following in a terminal:
sudo nvidia-settings
This will launch Nvidia's configuration utility. From there you need to click, "X Server Display Configuration" and click "Detect Displays" (assuming the HDMI cable is plugged in). Then it's simply a matter of configuring the display as per normal and applying the changes.