I presume the basic 128K service will at least get you up and running but I know nothing of Microsoft's Live infrastructure and whether this is sufficient bandwidth. In all fairness it should be more than adequate as the game data transfer volumes shouldn't be that high - although the voice-over-network could be a different matter.
You should be fine on 128K. The only problem may be the upload speeds if it is around 64K you may run into problems if a game requires high bandwidth.
You can get a good idea from server bandwidth requirements. For instance, if you are running a UT server, you require roughly about 64K per person for smooth gaming. So a 256K broadband connection would be adequate to host 4 people.
Therefore you would need a connection which could receive about 64K as well as send your infomation (usually considerably less as you only need to send your position). This at the moment is around the maximum bandwidth a game will require.
The higher speeds are more appropriate for browsing, downloading patches and software, which may be good reasons alone to get the extra bandwidth.