Solution 1:

See Apple's excellent FAQ on multiple App Store and iCloud Accounts: http://support.apple.com/kb/HT4895

Particularly these sections:

  • Using the same Apple ID for Store purchases and iCloud (recommended)
  • Using an individual Apple ID for iCloud and a (different) shared Apple ID for Store Purchases

Solution 2:

The iCloud login is separate to the App Store login. You can still log into the same App Store account but different iCloud accounts (for data syncing etc).

Disclaimer: I'm fairly sure this works, but have not tried it and am not aware if there are any caveats yet.