Do prepaid phones have issues with downloading certain Apps in the Android Market?
I highly doubt it's to do with being 'pre-paid' or not.

More likely, it could be from a number of reasons. Such as internet connection where carriers can limit the download file size.

I personally know that DL'ing larger files over the carrier network will fail unless it has a 'resume' or some sort of authentication feature.