I had the exact same problem and it was driving me nuts. I did finally figure it out and fixed it. I have XP Pro with a GEForce 8400 card which WAY more than meets requirements. It's like the game can't recognize the card's numbering system and says it doesn't meet requirements. It of course ran fine first try on my husband's computer.
What I finally figured out and what worked like a charm for me is:
1. Right-click your KOTR2 icon on your desktop
2. Left-click on properties
3. Go to the compatibility tab
4. Check the box Run this Game in Compatibility mode, select Windows 2000 from the dropdown box, hit Apply and OK
5. Retry your game
My windows login is also part of the Adminstrator group on my local computer so I didn't have any rights issue problems.
Happy gaming!