How do you have the XBOX 360 hooked up to the TV? If you hooked it up the same way you hooked it to your old TV, that won't work.
You should only be using either the HD Component Video cable or the VGA cable. You cannot use Composite Video or S-Video as neither are capable of carrying HD signals.
You should set the XBOX 360 for 1080i output in most cases. Your display is a 1920 x 1080 display, so it will de-interlace the 1080i and give you the full 1080p resolution. If you use 720p, the display will scale it up to 1080p and it will look softer as a result.
If your display has a VGA input and accepts 1080p over VGA, then you could try 1080p as well.