Celerons are complete shit no matter how fast they run. I learned this the hard way. Even the newer Pentium base chips (read: declawed core 2) at 1.8 ghz are much faster. So yeah, a cpu upgrade would net the most benefit here.
How much are you looking to spend?
Oh and not to brag, but I just ordered a Athlon X2 4000+, 2 gigs of Corsair DDR2 800, Corsair 450w power supply, Gigabyte 690G mobo, 160gig Western Digital HD, and a Centurion 534 case for $462.33 including shipping. =)