They actually just responded to my email outlining how to get it transferred to the new device...I'll post it here for anyone who might need it. I'm going to email them later tonight with my info, we shall see if they honor their own policy.
-----
I've received a new Android handset, can I transfer my free/unlimited app to my new handset?
Users who’ve downloaded and setup the free Shazam app prior to the 13th July 2010 can now keep their unlimited tagging status when switching to a new Android device. Note, users who purchase Shazam Encore can re-download Shazam Encore from the Android Market free as long as they use the same Google account on their new device.
To keep your unlimited tagging status, follow the steps below.
1) Note down the IMEI number of the Android device which had Shazam installed with unlimited tagging.
Trouble finding your IMEI? • If you still have the original device, the IMEI number can be found under Android Settings> About Phone> Status > IMEI. • The IMEI will be printed on a label on the device, usually under the battery. • Your carrier may also give you this information from their records if you have sold your device or lost it. • It may also be found located in/on the handset's original packaging.
2) Launch Shazam on your new device and click on Settings>About Shazam
3) Click the email address link (android.support@shazamteam.com). This will open up a pre-populated support email (containing your current MEID/IMEI) using your preferred email client.
4) Change to Subject text to “Android: Transfer Unlimited Tagging”
5) At the bottom of the mail, enter the IMEI number of your old device which was granted unlimited tagging.
6) Select Send
If our records indicate you were granted unlimited tagging on your old IMEI, we will transfer the same status over to your new device. Please note: Your old device will be reverted back to limited user status.