The problem with any download spec, is that the figure quoted is the maximum download speed. The NTL 600K download SHOULD be ok for xbox, but I have had serious lag problems in the past, purely because there were too many people in my area/street, all pulling data at the same time. When I measured my download speed, I was only getting 150K
Recently it has improved, and I'm getting 250K to 550K (depending on time of day)!
Another thing to take into consideration, is whether you want to be able to surf the web at the same time as playing on Xbox - if you do, then 512K may not be enough! (But I guess you already know this!)