I wasn't aware of that limitation. Although it does make sense to disable potentially data-hefty OBJECT or EMBED tags when on the cellular data service for which your provider may be charging by the byte, if that were the reason it wouldn't make sense that it would still work on 3G and only not on GPRS.
Perhaps the problem is one of basic data throughput? Not having an iPhone yourself (or myself) makes it difficult to test your colleague's statement.
Remember that GPRS is much slower than Wi-Fi or 3G. According to Wikipedia, GPRS will provide between 56 and 114 kbps of total duplex throughput, not all of which is in the download direction. You can already see that's not fast enough to instantly stream a typical 128 kbps mp3, even if you were getting the optimal throughput and getting it all as download speed.
Looking at this forum discussion as an example that came up on Google, the GPRS customers (the ones not using Telestra, which is an EDGE provider in that area) are getting around 40 kbps. So if as the question implies, you're stuck in EDGEland, NOT 3Gland or anything inbetween, it's going to take about 20 seconds of buffering to play a 30 second mp3. And when you use a behaviour-ambiguous tag like OBJECT or EMBED, there's no guarantee in how the browser will interpret it and whether it's going to try to intelligently stream the file rather than having to download the whole thing before starting it.
So, it's quite possible your colleague just didn't wait long enough to see if whatever embedded media he chose as a test started to play (assuming he wasn't using your 17KB test mp3 there). It's also possible that the iPhone does indeed have this limitation, though I'd think Google would be more forthcoming with it than my quick search uncovered, since people have been vocal enough with other things they don't like about iPhone. Another possibility would be that it's a limitation in the build of Safari that currently ships with the iPhone which might be changed in future versions or in another browser.
Ultimately though, the question is, what kind of user experience do you really want? Embedded audio on GPRS is going to take a long time to load, and users aren't going to enjoy the experience, or potentially even experience it at all if it's supposed to start playing on page visit and it doesn't load before they navigate away. It might not be a goal worth striving towards in that case.