If it’s both MKV and AVI giving you grief, then it’s not going to have anything to do with remuxing your MKVs.
Here’s a test for you.
If you have a memory stick,
Format the memory key in Windows (or your OS). Format it as FAT32 if possible.
Copy a small movie onto it. Make it something like a DivX/XViD.
Make sure you safely remove the memory key!!!
Unplug all your other USB devices from the media player, and just plug in this memory stick.
Turn on the media player and let it scan for new files.
Once its finished, navigate to the memory stick, and execute the file off it.
At this point, I’m expecting you have a working video file?
If so, then the issue relates back to your storage drive again. Now it’s unplugged from your media player, take it back to your computer and plug it in.
Open My Computer (or Windows Explorer).
Locate the drive letter
Right click on the drive letter and select ‘Tools’
Click ‘Check Disk for Errors’ (or whatever its called)
Let Windows fix any errors it finds (let us know if it does find errors)
Eject the drive safely and return it to the media player and try again.
Let us know if you still have problems.