Tim K - this all depends on the specific laws of your 'Host' country!
If you purchase a product that does not CLEARLY state it will NOT WORK on your hardware configuration - you have an excellent case for RETURNING the game and RECEIVING A FULL REFUND.
If SEGA have sent a communication admitting this, they have no legal recourse - they have to offer you your money back!
I would try the retail outlet first, take a copy of the mail with you - if they don't give you a refund - contact SEGA directly.
Check the SALE OF GOODS ACT, for the country you are residing in, this should give you a clear indiciation as to your consumer rights!
Ryan - If you don't mind - could you let us know how you get on? (if you decide to take back!)