Submit Podcast - 1st Time - Host does NOT support byte-range requests

You're the third person to come against this one recently. Earlier to day Robert Walch posted about it in this thread, which is worth reading:

https://discussions.apple.com/thread/3930300?answerId=18316651022#18316651022

The subscribing test is irrelevant because it involves only a simple download; the problem apparently arises with iOS devices which use the Store rather than subscribing. I don't know whether all this is a sudden change by Apple - it may be, because there have been a lot of complaints about iOS devices failing to download podcasts, with, up to now, no apparent explanation.

it may well be that your only option is to find another hosting service which can handle this.

To be fair to Robert, I don't think there is an easy resolution: at least he can recommend a service that has this facility.

You recommend "another hosting sevice." Which one?

That's the problem. There's no way of knowing without either asking them first, or trying to submit from a particular service and finding it's rejected for this reason. This appears to be a recent change by Apple, probably because of the iPhone problem, and it's going to be a bit of a stumbling-block.

does anyone know what "byte-range requests" means?

I certainly don't, though when I have a chance I will try to find out, but this is server technology and as such is over my head - most other people's too: I will offer a guess that for streaming purposes it means asking for a part of a file, then waiting, then asking for the next part, and so on, rather than just requesting the file in toto. This would seem akin to the ability to resume an interrupted download.

It will probably be a question of asking hosting service whether this applies, and if they say 'no' (or don't know what it means) finding another hosting service.

I did a bit of research, including this article -

http://en.wikipedia.org/wiki/Byte_serving

Basically it confirms my guess - the process calls only sections of a file at a time rather than the whole lot, and is apparently required for iPhone to be able to play podcasts.

As to HostGator, whatever they say it would appear that their server doesn't support this. (The problem lies with serving the actual media file, not the feed, though it might be compounded if you are using some sort of scripting to access the file rather than the direct URL). If they can't sort this out your only option would seem to be to look for another hosting service, checking with them first that a) they know what it is, and b) they support it.