This is the kind of question that you want someone else to answer, for all sorts of reasons. Though, in the absence of better informed and more technically knowledgeable folk, I will give you my two pence worth.
It's been a while since I was on ADSL (or seems so at least) but I'd say 600k up is all right for gaming. I'd normally say it's more about your latency and jitter (variability of latency as I understand it) than sheer throughput (bandwidth) though of course having adequate bandwidth does matter but I think 600kbps is adequate enough. Your latency might be a better benchmark to go by, but...
You're playing on the Xbox 360, a console. And there can be huge issues involved with what is termed 'match making', that is grouping of players in a game (supposedly) dependent on their average latencies. If a game is hosted by another player rather than at a common and separate server on another line somewhere, then you can sometimes be at a disadvantage if you've got better latency than others and are the host. But this depends on the game.
So far, it's been Call of Duty and Battlefield games that have been particularly criticised for unfairly penalising users who are hosting games due to seemingly overly aggressive 'latency compensation'. If you're hosting a game on your device then you're effectively 0 milliseconds away in time and would expect a bit of an advantage over other players depending on how far away they were from you (and their latency). I don't know if this applies to Gears of War 3 though. Timey used to play that a lot so he might know.
Things to check are your 'ping'. On a PC you can run a command prompt from the run box by typing cmd and pressing enter. You get a black dos-like box and you just type: ping bbc.co.uk or wherever to see what your latency is like (how many milliseconds it takes for a packet of data to get there and back). You can also ping a game server if you have the IP address. What you want to see is a nice steady ping without any spikes or packet losses (time outs) and preferably as low as possible, something under 30ms would be very good but you can play games okay up to about 130ms in my experience without being so severely affected by 'lag', the game becomes unplayable as you're too out of sync with what's going on.
Best to post router (line) stats and do some ping tests. There are various online sites and tools which help. And lastly, most of suck at gaming online here at least some of the time. And some all of the time (or so it seems). It's taken me over 100 hours on Battlefield 4 to get more competent at it to start scoring in the top half of the rankings. I'm not a hardcore gamer but I'm experienced in some of the older Battlefield games so have some advantage over totally newcomers. You've got to give it time no matter how good you are to understand the mechanics of a game and in a game like Call of Duty or Battlefield you need to understand the map as well and how it's being played like watching for players re-spawning on squad members and understanding where the hot spots are going to be.
I guess you're playing Horde mode so that might be a bit more simple, I don't know? Even a simple game will have people who are amazingly good at it as they've been playing it loads and it really requires online experience to get good against other human players. Bots don't compare at all to real intelligence. Even Nelly and Swanny can outwit the average bot sometimes. Just checking if they're reading this. I doubt it. And Timey won't be either. But you can't be as bad as him.
Edited by deleted (Sun 22-Dec-13 21:31:37)