(1) The color (or lack of) has nothing to do with the usability. In fact, if color does aid in use then you probably have a larger accessibility problem.
(2) I think you are biasing your opinion too much toward the first-use of an application. Yes, associating icons and labels does aid in learning and first-use, but has little effect on usability long term for regularly used applications. With that said, the in-app icons you are referring to are typically straight forward (add, search, remove, etc) and, in my opinion, are understandable on first use as well. There are occasionally poorly designed third party apps that do have obscure in-app icons. But, this is not typical of the platform.
Everything being the same color can easily lead to a feeling of being "in a maze of twisty passages, all alike". It's like gray dialog boxes that pop up more gray dialog boxes: technical users tend to have an ontological hierarchy in mind as they navigate so it's no big deal, but most people get quickly overwhelmed and feel lost/overwhelmed. [Not that I'm saying that simply coloring dialog boxes differently would necessarily help here! Just that them all being gray adds to the overwhelm.]
I strongly disagree that color aiding in use points to a larger accessibility problem — perhaps you just mean that if color is necessary for use you've got a problem (which I'd certainly agree with), but while I could get by in my everyday world with monochrome vision, I'm glad I have color cues all around me that aid me in distinguishing amongst objects quickly and with minimal effort.
Yes, you are right. Color when used appropriately can improve the use of a UI. But, he/she implied that it was unusable simply because the icons lacked color. That is completely wrong.
My wife has a win7 phone, very similar with the huge icons (part of the reason she bought it was she could see it without her glasses on). However, I hate using it. My android phone isn't what I'd call intuitive, but I do know exactly how to get where I want to go, ie: push the expanded apps button, scroll around for settings. Took about 4 times to find the right settings button for bluetooth on the win7 phone, I knew pretty much where to go immediately on my phone from the start.
So...I'd say ease of use is high as long as you only want what is on your home icons, but not so much after that.
It is just Settings > Bluetooth on WP7. Pretty easy. I do wish they would allow you to pin settings to the start screen. That would be nice for WI-FI. But, to your point, Android and iPhone seem unintuitive to me because I don't use them on a daily basis.
(2) I think you are biasing your opinion too much toward the first-use of an application. Yes, associating icons and labels does aid in learning and first-use, but has little effect on usability long term for regularly used applications. With that said, the in-app icons you are referring to are typically straight forward (add, search, remove, etc) and, in my opinion, are understandable on first use as well. There are occasionally poorly designed third party apps that do have obscure in-app icons. But, this is not typical of the platform.