Is it possible to make one processor look like another?
It's not impossible; Intel CPUs have had the ability to have new microcode uploaded into them for some time, and there are open source programs that can do so. If someone can then decipher the microcode, they could then produce modified microcode with a different CPUID
string embedded in it. (It's supposed to have a checksum to prevent that, but I wouldn't be surprised to find the checksum is validated by the update utility and not the CPU itself.)
"Celeron" is a brand name which Intel has applied to dozens of distinct processor designs. In particular, a number of dual core processors have been sold under the name "Celeron" (which, in Intel-speak, means "cheaper and reduced", but not necessarily "mono-core"). So your sales guy may have sold many Celeron "posing" as dual core processors because they are dual core processors, so such posing is trivial.
That being said, if the sales guy just admits having swindled dozens of customers, then how what he says can really be considered as trustworthy ?
On a theoretical point of view, since the BIOS is the first thing which runs in the machine, there is little that can be done to fool it about the processor (unless adding an extra hardware piece between the processor and the motherboard, which looks very expensive and thus useless if the goal is to sell overpriced Celeron). More realistically, the BIOS itself could be altered: it is stored in Flash, not ROM, hence it can be changed with a software-only one-time operation. BIOS hacking is not especially difficult (it requires a bit of reverse-engineering, but there is nothing really protected there). A hacked BIOS could report a distinct processor from what is really installed.
Using a rootkit someone can make their hardware appear as anything. The amount of memory available or processor speed/type can be easily influenced. This is very useful if you want to store data on the drive whiling hiding its disk usage. Hypervisor rootkits work on modern systems, you should check out the Stoned Bootkit.
The QEMU Virtual Machine can be used to emulate a wide verity of processor architectures. You can also specify your own a bios image to boot from. For instance a QEMU VM can use coreboot which is an open source bios.