I agree with what I take to be the general message of previous comments: the most important thing is that you handle this professionally. I don't think you need to make a decision about switching just yet. You can try following up with him, see how it goes, and continue mulling over the options during your attempt to establish a better working relationship with him. Then reevaluate your options after you see how that goes. Here's my advice, FWIW: start by emailing your advisor to request a meeting. This email is an opportunity to shape his perception of you, so I would use it as such. Don't convey any shock, hurt feelings, etc. Instead, say something along the lines of (1) you appreciated the candor of his remark about your commitment, and (2) you would appreciate the opportunity to discuss this further. With respect to (2) try to be neither defensive nor self-deprecating -- you don't have to give any indication of whether you think his perception is correct or not -- instead frame your interest in learning more as one motivated by an eagerness to grow and learn (in other words, you want to discuss this because you're *always* looking for ways to improve and you take criticism as a valuable learning opportunity). I don't think it matters that much exactly what you say in your email as long as you maintain a professional tone. Remember, academia is a harsh place and thick skin is required to survive in it!
If he blows you off (doesn't reply, gives you 5 minutes in between his other commitments, etc.) you will have gathered more data about his willingness to invest some of his time in working with you, and you will have demonstrated an adroit response to criticism. If he doesn't blow you off, then carry the same professional demeanor into your meeting with him. I would try to hear him out, keep your composure even if what he says feels harsh, and avoid any defensiveness. You're not likely to change his mind by pointing out that he's wrong (even if he is), so your best bet is to try to impress him with how you receive the criticism - maturely (you nod and say "I see what you're saying" or "I understand how it could seem that way" etc etc) not dramatically (displaying anger, hurt feelings, crushing disappointment, etc).
In terms of your feeling misled...since he sounds like the I'm-such-a-big-shot-I-can't-be-bothered type, I doubt you'll get far by voicing that complaint. I'd say either find a way to get the most out of whatever projects you actually can work on with him, or switch advisors. If there's no way you can work up some more enthusiasm for anything other than a project he's not going to give you, then I don't see how you're going to get along with him. It does sound like he might be a Mr. Important type, but even if he's a pompous jerk there's still something to be said for looking at things from his perspective. He most likely IS very busy and really does have overwhelming demands on his time. He doesn't want to deal with students who aren't self-motivated, taking initiative, showing enthusiasm, putting in a lot of time and effort, and so on. If he senses that you aren't into the work you're doing with him, he probably finds that irritating or at least a reason to be dismissive. Even nice, generous-with-time profs often have that sort of reaction.
OK that's way more rambling than I intended. Whatever you decide to do, hope it works out for you and best of luck!