I ran into something like that this week as well. Really was beating my head against the wall. After doing the sort of things you tried I discovered this post today. Doing these instructions seemed to resolve the final issues I was having (e.g. Plex worked fine on iOS but not AppleTV).
I don’t think this was the root cause - my issues happened right after installing the most recent DSM Update. Not sure though, at least it all seems to be working now.
Note: after uninstalling Plex I also had to follow the info in this post to get Plex going at all.
