The times I've seen this it was because the device could not access the icons at the URL specified during the push. This
article talks about pushing the icons into cache, but even if you do that they should still be accessible by the URL for when the cache gets cleaned out.