WinMe is offered in 3 ways:
Promotional upgrade (for only Win98, Win98SE only)
Upgrade (for Win95, 98, 98SE)
Full (duhhhh)
While the promotional is usually found for $50, you must already have Win98 or Win98SE on your hard drive. You can only upgrade on top of your current O/S! (VERY BAD IDEA)
The "upgrade" version will allow you to install on a new/fresh format hard drive. You will however need your Win95, 98, 98SE CD available because it will ask for it while doing the install. It needs it for verification. This can usually be found in stores for around $90.
The "full" version is overpriced and not needed if you own a prior WinX O/S!
Like IamDavid said.... make sure it's a clean install. Since it sound like you are building a new PC, I suspect it's a newly formatted H.D.
So the question is.... which upgrade version do you own?