HI Kiderz,
Sorry to hear about the Dreamcast problem.
Whats probably ahppened is that your old tv had something called PAL 60.
I had a similar experience when i modded a megadrive and noticed that on some tvs the picture was in colour and at full screen using the rf.
Pal 60 is a useful adition to a tv.
Saying that if your new tv has got a scart socket i STRONGLY recomend using this lead.Most modern tvs with scart cater for RGB which is what the lead outputs from the Dreamcast.
This should cure your problem very quicly.
The highest quality i have used is a Dreamcast VGA box which lets the machine run on a pc monitor.
The machine already has vga output internally and it looks stunning.
Ebay is ideal for scart leads and there are many other places you can obtain them from.
If you have no luck i have some in my cupboard and they are brand new.
A good way to test your new tv is with a dvd player.
You can try using the dvd player using RGB output,If its in colour the dreamcast will be fine.
Hope this helps,
Ian.