I got some more info on this issue. I am starting to suspect there's something weird going on with the way the player deals with the interleaving settings of the mp4 file. In particular, given the file 00.mp4 (which is not working), I generated a new file from it using "MP4Box -cat" the only thing I changed was the interleaving setting: "MP4Box -inter 1000 -cat 00.mp4 -new 20.mp4". This worked fine, 20.mp4 played without errors. I then used an interleaving setting of 500 (ms), this is a default setting and the problem reappeared. After playing around with this setting, I figured out that some of them work and some don't. For example, anything from 450 to 950 range doesn't work, 1000-1400 works, 1500-1900 doesn't. It seems to work better on high (several thousand ms) settings. I am currently setting it to 2000 ms.
I don't think this is the end of it though. The problem probably has something to do with the network latency, while it seems to work fine in my local network, it might behave differently from a remote host. I can't test that right now but I'll do it (test from a remote host) in a day or two. It will be interesting to see the results.
Here's the most important part - I don't believe this problem existed prior to the Roku 2.8 firmware update. In fact, I am quite sure it didn't exist because I can no longer play the files (since Nov 09, 2010) I used to be able to play. I wanted to positively confirm this. In order to do so, I needed to downgrade to the previous version. I don't think there is a "legit" way to do so. I tried resetting the box but it seems to either not reset the firmware version or update the firmware upon the first initialization. Either case, I couldn't get back to a release prior to 2.8. If someone could let me know how to do so, I'd really appreciate it.
This circles me back to the original question - is there a way to find out more (from the logs, special undocumented features, etc.) when the following error is encountered?
"play failed: An unexpected problem (but not server timeout or HTTP error) has been detected"
If I could determine why changing those interleaving settings in an MP4 container causes this problem, I could be able to open a meaningful bug report.