The alert (which stops sync, Gmail from notifying you, and play store from installing apps) comes up when your internal storage (in /data/app) reaches 25% of capacity. Depending on the total available storage (100mb, 2gb, 16gb, etc) the trigger point can be very different. I used to see this often with cheap prepaid devices once I hit 20mb remaining, but larger capacity phones can have it come up with a gigabyte remaining.
My iPad 3 told me I ran out of space to install a 100mb app even though going to settings showed 2gb left.