Nokia's note is just inefficiently applied boiler plate. The part that alarms you is the part about 'out of warantee ' charges. Since you say it is brand new, I doubt it is out of warantee.

But returning it to Circuit City for another one or for a refund sounds quickest.