Either remote should work with any player (Mk1, Mk2, Mk2a(RioCar)). Some Things to check:
1) Take the red plastic tab out of the remote to activate the battery.
2) Make sure you're running 1.03 or higher.
3) Test the new remote. You'll have to have some other device that can read IR, like a learning remote control, handheld PC with Remote control Software, or even a video camera that can pick up near-IR (you'd be surprised how many video cameras can see IR); even Radio Shack used to carry a 1/2 business card-sized IR tester. When you hit it with IR, you can see little red dots on it.
3) Test your Mk2's IR reciever with your old remote.

If you can't verify that your new remote works, try it with a new battery (CR2025 or compatible), then email [email protected], as they're the only people that can replace it for you from stock.

Good Luck!
Jason