He should be eating micro-algae - and some macro algae as well. Some urchins are herbivores, some are pretty omnivorous, and some can be un-reef-safe carnivores - a friend of mine watched one devour his feather dusters many years ago.
For feeding, I'd be tempted to try a sheet of nori, folded underneath the urchin. (You could add some mysis or other meatier foods between the folds of nori, as well.) I'd guess that you could place that next to / under the urchin, or just set it on the rock and place the urchin on top of it.
The fading of this guy's color concerns me - it just doesn't sound good, and I don't know enough about them to tell you why - or what to do about it.
~Bruce