iCal iPhone change Exchange calendar color
On iOS 6 and Office 365 - exchange calendars are fully customizable as long as you like the 7 default colors. :( - which means, you can't customize the colors on iOS as you clearly stated in the question

The only interface for changing colors uses the default picker - Go to the Calendar app, tap Calendars in the top left, scroll to the calendar you want to modify, tap the blue circle with the white > symbol and then choose any of the colors that are listed.

Perhaps an update to exchange or to iOS will fix this in the future, but you're not missing anything obvious. Even using alternate apps like Fantastical or Agenda on iOS won't help you escape the limited color palette.