Did you have a new blade cut as well or just the fob?
I had a key cutters cut me a new blade that wouldn't turn the lock, turns out the new blade was a slightly wider towards the handle and fowled the lock. Trimmed it down and it worked.
If not, have you tried some anti seize spray? WD40 like. Don't twist too hard, that's how I broke my key blade! If that works spray some lubricating oil (not WD-40) in there afterwards.