I'm not sure of what type key the new lock uses, but if possible, I'd take it to a locksmith. Then you not only get to remove the lock, but you'll have a new key as well.

Just sayin'.