There is a thread over at XDA with few users who also couldn't unlock theirs. You are the first one I hear who wasn't able to unlock it with "official" codes provided by Verizon. Really strage!
i've unrooted to see if the codes work, no dice.
anyway, i requested they obtain a new lock code, hopefully it will work.
the foreign sim i have has a slightly different printed board arrangement than the one that comes with the phone (4 contact rows, as opposed to 3), but i don't think that makes a difference.
i know the card works fine in my GSM phone and registers on cingular ....
last resort would be to swap out the phone .... maybe there's a defective batch out there