It’s been my contention that the US Army is recruiting in the wrong places. For example, there are vast amounts of kids learning the military skills of shoot, move, and communicate in paintball fields all over the US. If USAREC (also known as USAWRECK) was smart, they’d sponsor local competitions and scenarios.
If you're talking about video games, they already have America's Army. But you're right, they could improve on that by holding competitions. It would also be cool if they came out with a console version for at least the Wii and XBox 360 (highest market penetration amongst the younger).
OTOH, the console one probably brings up regulatory problems. They have to pay a lot in licensing, etc., and have physical media shipped. It would probably cost too much if the Army doesn't charge, and I don't know whether it'd be legal for them to charge.