What you say there is true, if he wants to game, GET THE CELERON D!! They have come a loooong way since the first p4 based Celerons. The new ones are fantastic overclockers. I know someone (a fairly amateur overclocker) who has a Celeron D356 @ 4.2 with stock cooling!
Yes, the newest Celeron Ds (those on 65nm with 512K cache) are good enough; basically they're old P4s. On the ther hand, the sempron 3200+ is also a great value with around $65. Getting it to 2.7G on stock is 50% OC while 4.2G is still 26% of the CD 356. Socket 754 semprons were not good @ OCing given the 130nm process but the AM2 ones are sometimes better than athlons with the cooler temps.
The new Celerons arent like old P4s, they have 30 instruction pipelines (i think that's what they're called) , the Northwood (the one with 512k Cache) had 20. It was a more efficient architecture than Prescott (which the new Celerons are based on).
But as you said, a Sempron would also be a great idea! Or if he could afford the $100 or so for a 3200+.