Sparse Bundle image is mostly used for Time Machine over AFP or NFS. It is a disk image that only takes up the amount of space actually used for its contents.
Not entirely true. Most people don't know that if you delete files from this image, you need to compact it afterwards otherwise you will see the image as full.

The same thing happens also when Time Machine needs extra space and deletes older backups. If you do not compact the image after you get for the first time this message, Time Machine will delete almost all backups and you will still get this message.

In this situation, the only thing to do is to fire up a nice hdiutil feature, compact:

osx: root# [color=green]hdiutil compact Time\ Machine.sparsebundle[/color]
Starting to compact…
Reclaiming free space…
...........................................................................................................................................
Finishing compaction…
Reclaimed 167.3 GB out of 213.2 GB possible.

Now, the best practice is to do this periodically, to avoid getting in this situation (via crontab for example).