I've experienced this with new tires from time to time. I read (on this forum I think) to leave them out in direct sunlight and try again. Makes a ton of difference (provided you have a source of warm, direct sunlight).
FWIW, I've never had an issue taking a tire off that was difficult to get on.
FWIW2, I prefer snap-on rim strips to tape these days. I've had really good luck with Specialized's strips. Nashbar's are a bit wide but still work ok. Giving Ritchey a try on my current build.
