"Tried changing the resolution and all that" is a bit vague, but a good starting point.
As you probably know, flat screen monitors or TVs (unlike the older CRT monitors) only really look good at one particular resolution.
A 1080p monitor is working at 1920 x 1080 resolution.
A 720p monitor is working at 1280 x 720 resolution.
So your starting point is to pick the right resolution. Now, having said that, there are some other potential issues I have encountered:
I have a Samsung 23 inch monitor / TV that is 1080p, and for whatever reason the computer looks like crap when it is plugged in via the HDMI input. But it looks great plugged in through the DVI or VGA (PC) inputs. I have no idea why.
But then plug that same computer's HDMI output into my Toshiba 40" 1080p TV, it looks great at full 1920 x 1080 resolution. But the Toshiba's VGA (PC) input only supports 1280 x 720. I found that hard to believe until I confirmed the info, buried on the last page of the Toshiba's manual under "supported resolution".
So bottom line is:
* Experiment with the resolutions and get the right one to match
* Try your computers output in another TV or monitor to make sure its not the source that's the problem
* When all else fails, read the manual.... carefully.
I hope that helps...