The very old double-edged sword.
Many companies will have no problem altering or retracting a verbal offer, but if you should do the same you are a pariah. Legally there is no offer until you see it in writing (as the company will be happy and quick to point out) and in this industry, verbal commitments are as as good as vapor. That being said, BZ is right. If you break a verbal commitment, the company and its wandering parts will probably hold it against you forever (until they really need you to fill a slot they can't.)
As for interviewing you when you already have a verbal agreement with someone else, I am not as surprised as you are. The new company is aware of the ethereal nature of verbal agreements and the propensity of companies and individuals to ignore them when convenient. They may think the odds are good enough that either the first company will back out or you will if they make you the 'offer you can't refuse.'
The bottom line is that even though there is a double standard at work you have to decide what your word means. I accepted an offer (not written, just verbal) at a utility and within a day or two was offered more money to work for a contract company as a training coordinator, a job I really wanted. I ended up staying at the utility for 13 years... probably would still have made more money for the contractor, but I don't regret the decision. My word means a lot to me.
An afterthought -- I recently was faced with a similar decision. I had committed to an outage for a large player in the contract HP industry and was offered a long-term (but temporary) job with a utility (who happened to be one of the contractor's clients.) I contacted the contract company, explained the situation and told them I did not want to leave them hanging or break a commitment to them. They told me they understood and did not want to stand in my way of doing something that I really wanted. I took the long term job after getting their 'blessing' to do so. I will probably work for that contract company again sometime and I don't think I will have any trouble doing so.