Solved - (Sort of)
1. Delete the iCloud account from your iPhone (Settings > Mail, Contacts, Calendars > iCloud > scroll to bottom > Delete Account)
2. Add your iCloud account to your iPhone again by going to Settings > iCloud and enter in your account info.
This will automatically add the iCloud inbox to your mail app, you don't need to add the account again in the "Mail, Contacts, Calendars" Settings.
This process will result in you having only one iCloud inbox, though I had to go in and re-enter my password in the Mail, Contacts, Calendars settings for iCloud once the account had been added.
I'm still getting the occasional password error, "The user name or password for "iCloud" is incorrect." when i check my mail, but it may be due to the server, not the device.
Best of luck!
Hope this helps!