What's wrong with the Celeron CPU?
To stay at around that budget with a different you could compromise on the motherboard or go AMD, but it's a fairly powerful CPU IMO.
I'm looking at around £500 for a Dell Inspiron, with a faster CPU, smaller/lower resolution monitor, worse graphics card, and Vista (compared to the first build with no modifications, this is). A prebuilt machine is usually not so upgradeable either - "they" usually give you a PSU that's just adequate for the job, and a motherboard with sometimes few expansion slots, so to upgrade would often cost too much to be worthwhile.