Android Contacts no longer syncs multiple accounts?
First, make sure that you have added both accounts to your phone under Settings -> Accounts, and enable contacts sync on each one.

While in the Contacts app, begin adding a new contact by tapping on the "+" which brings up the "Add new contact" screen.  Directly under the contact photo, and above the contact name there is a "Saving to" box, which is a drop-down that can be accessed by tapping the down arrow to the right:


This drop-down should contain all your other accounts that are synced:


Select the account you wish to save this contact to by tapping on it, fill out the contact details and tap the check-mark on the top-right to save it.

Keep in mind that other contact management apps will most likely have a different way to save contacts to different accounts.