In addition to Rich's excellent advice, you can call MS Customer Service and ask for their help in replacing the OS. They have a program where if you document a legit purchase which turns out to be non-Genuine they may replace the OS for free.
If not then I would replace it with Builder's OEM since that is what you originally bought which turned out to be non-Genuine. However Ultimate is considerably more expensive and most users do not need the few extra features it offers, so I would go with Home Premium similar to this: Amazon.com: Windows 7 Home Premium SP1 64bit (Full) System Builder DVD 1 Pack: Software
Boot the DVD to clean reinstall following these illustrated steps during which you should Delete all partitions, Create New ones as you wish, or just click Next to begin install to let the installer create/format the install partition for you: Clean Install Windows 7