Maybe your phone just isn't updating your iCloud stats as fast as you expect. After deleting your pictures and videos, did you try logging onto your iCloud account on the web to check your available storage, or just view it through your settings on your phone?