ICloud

When you had the phone did you upgrade your iCloud storage and you haven't since cancelled the upgrade ?

You should be able to cancel/downgrade it via a computer or iOS device - from http://support.apple.com/kb/TS4009 :

iOS 5 and later

1. Go to Settings > iCloud > Storage & Backup.
2. ap Change Storage Plan.
3. Tap Downgrade Options and enter your Apple ID password.
4. Choose a different plan to use when your current storage plan expires.
5. Tap Done.

OS X

1. Choose Apple () menu > System Preferences, then click iCloud.
2. Click Manage in the lower-right corner.
3. Click Change Storage Plan in the upper-right corner.
4. Click Downgrade Options.
5. Enter your Apple ID password, then click Manage.
6. Choose a different plan to use when your current storage plan expires.
7. Click Done.

Windows 8, Windows 7, and Vista

1. Open the iCloud Control Panel:
   • In Windows 8, go to the Start screen and click the iCloud tile.
   • In Windows 7 and Vista, choose Start > All Programs > iCloud > iCloud.
2. Click Manage.
3. Click Change Storage Plan.
4. Click Downgrade Options.
5. Enter your Apple ID password, then click Manage.
6. Choose a different plan to use when your current storage plan expires.
7. Click Done.