These achievements have become much harder due to the patch that came out in early 2008 that barred 2 people doing it by themselves on the same team. You can no longer have a 2 vs. 0 match and get this achievement for two people at the same time. The games must be a minimum of 1 vs. 1, so you will have to boost 500 games total, 250 wins each. A CTF game is the fastest way to get wins.
Warning: For some reason, the game likes to reset wins or just forget about some of them, so it is suggested to do all 250 wins in one sitting, or no more than 2-3 sittings. It will take a while and be very boring, but if you're taking turns it shouldn't be too bad.