Why can I not backup my replacement iPhone after restoring an iCloud backup?
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).