Are you running at 1080p or 1080i? It sounds like interlacing lines to me (1080i)
Look at the edges in this photo - is this the kind of thing?
1080p should be 1920x1080@50Hz.
If it's 1080i, it will be 1920x1080@25 or 30hz (30Hz is even worse than 25).
Justin