I am sorry you are having trouble with this map but I have never heard af anyone having this problem? Does it also do this in the BR version? Have you tried deleting coyotebluff.pk3? Then you can just extract it from the download & put it in your westernq3 folder again. Do you have more than one pc you can test on? Maybe try on a friend's computer?
@godsmack: By the way, did you try playing on one of the public WQ3 dedicated servers ? If you can (with autodownload On), maybe we can expect an "invalid pk3" message from the server ? who knows ? Then, we will have more clues. As Breli suggests, it does not hurt making a screenshot of your westernq3 folder ... (and possibly a checksum of each files )