I am using an iPhone 5S with the most up to date iOS software (9.2.1 currently) and having the same error.
I called Apple Care to get an answer on this - as I'm having the same issue. Downloading podcasts then when trying to play them I get the error message "Episode temporarily unavailable", even ones I have downloaded and played previously. I also didn't think the approach of having to download a podcast twice is an appropriate solution - even this doesn't always work.
The main Apple Support person I spoke with contacted the Apple iTunes Support department. They provided the following comments:
It isn't the player that is causing the issue its the third party providing the podcast file. The issue is that with new software updates to the iPhone or iPod the podcast files must also be updated.
Apparently part of the podcast download file needs to be re-written in order to be compatible with the newest Apple software update.
This doesn't really make sense as music files don't need to be updated everytime there is a software update (that I'm aware of anyway).
I called them back in order to try and delve a bit deeper into this issue.
I got a Senior Advisor on the phone - they checked my IMEI number and software version which seemed to be fine.
I got them to download the same specific podcast that I was having the issue with and they were able to play the one that for me was "unavailable" even though it is downloaded locally.
We ended up resolving it by deleting all the podcasts from Storage (Settings>General>Storage & iCloud Usage>Storage>Manage Storage>Podcasts)
and also Reset>Reset All settings (this will mean you lose all your settings - this didn't really affect me - just meant I had to put in my wifi password back in, reset my wallpaper and my alarm clock).
Hopefully this works for you - I asked that the Apple Advisor I spoke to pass this information onto the team at Apple that works on the Podcast app - hopefully they will be able to push an update to the app that makes this resolution process obsolete.