Why can I not backup my replacement iPhone after restoring an iCloud backup? I replaced my iPhone 6 with an identical phone, restored the most recent backup from iCloud.  I now cannot backup to the cloud without adding more storage.  Why?
Go to Settings > General > Usage > Manage Storage (iCloud) and delete the backup for your old phone.   The new phone will overwrite it own backups, just like the old phone did.  It won't overwrite the backup for another device (I.e your old phone).