When I installed the cifs driver and a third party player on the Kindle Fire, all of these videos play fine. Therefore, I know this is definitely a plex on Kindle Fire issue. Is there an ETA for fixing this issue on the Kindle Fire?
Is there any way you can share a video for us to test with, and/or provide a logcat of the video playback?
If the file is MP4, and it's optimized for streaming, those should Direct Playing.