The setup you're describing should work just fine--HDMI is basically a rearranged DVI signal with some extra stuff, and I'm personally running a 1080p TV off the exact same adapter connected to a Mac Mini, and it works perfectly.
The first question is whether the Mac is showing the correct model of monitor--that would give a hint if it's having trouble detecting what it's connected to.
The second question is if you see "1080p" listed in the resolution options; when attached via HDMI to a 1080p monitor I believe that should be in the list. Alternately 1080x1920 at the correct scan rate for your monitor should also work, but you say you're not seeing that. What resolutions DO you see? (SwitchResX and similar "pick unsupported resolutions apps can work around not having the correct resolution showing up, but shouldn't be necessary.)
Also make sure that "Overscan" is checked in the Options tab; without that on, there will be a big black border around everything, and the output signal won't match the TV's resolution precisely.
Third question is whether that monitor/TV has a "dot by dot" option, or something similar, in the aspect ratio settings (where you pick how a 4:3 signal is stretched to fit). If that's not on, the signal from the Mac will be stretched slightly, which both cuts off the edges of the screen and has the pixels not lining up properly. If the edges of the screen (menu bar and dock, that is) line up with the edges of the physical screen, then you will know that this is set right.
Fourth is to make sure that the TV's settings are adjusted properly. Monitors usually don't have adjustments for sharpness, brightness, etc, but TVs do, and if those are wrong the image from a computer can look TERRIBLE. Sharpness in particular can wreak havoc; depending on the TV you may actually want to turn it all the way DOWN, not up (my Sharp is like that). Whatever the setpoint at which it doesn't do any sharpening is what you want--usually if you display an image on the screen with 1 pixel high lines (look for an HDTV calibrator image), when the sharpness is set correctly the lines will all be visible and will look crisp. Similarly you want to have the brightness and contrast set right so that black and white are the right levels; looking up an HDTV calibrator (or downloading a calibration disc) can help you do this.
Last, when the TV is set up right, do the calibration thing in the Color tab of the Displays pref pane; that can make a huge difference on how color looks on any monitor, and is a must.
All that said, if the monitor has a DVI input it would really make more sense to get a mini-DVI to DVI adapter and just connect that way, since there's no advantage to using HDMI over DVI from the Mac's output, and it might bypass the TV's settings since it will be expecting a computer to be connected to that input. There's also the off chance the monitor is broken, but if you're getting something it's probably working ok.
