My 04 just did the same thing...at about oh let's see 36000 miles! I was on a trip when it happened and was out of warranty when I got back. Well, the Toyota dealer I bought it off of is going to pretty much honor the warranty and even gave me a loaner car to use this week.
Anyway, according to them they think there is a vacuum hose problem buried underneath the dash on the drivers side which has closed a valve that allows the cold air to flow. On the passenger side it's ice cold but hot air on the drivers side. They should have it fixed by Friday and I'll repost here to let you know what they found.