Apple has now started making the ability for the server to handle 'byte-range requests' a requirement. This means the ability to request part of a file at a time, rather than the whole thing, and is the method used the the iPhone plays podcasts from the Store.
A number of servers don't provide this, and it was leading to a spate of complaints that podcasts would not play on an iPhone, though they were OK on a computer. As a result, and to prevent this, you now have to use a suitable server.
I'm afraid that if your hosting service cannot provide this you will have to find another one. You should start by taking it up with them. Failing that, you need to ask any proposed hosting service whether they accomodate this, and if they say 'no' or don't know what it is, find another.