I dout Naev still reads these forums, but in case anyone else comes here with this problem, we figured it out today, and now I know why I never saw the problem. It's because the system language settings weren't English. If they're something else the game won't be able to find the files apparently.
So in the short term you can fix the issue by changing your LC_ALL=C and LANG=C env. variables. In the long term, has anyone ever heard of an error like this? I'm guessing I need to deal with unicode or such, but if anyone else has seen this and can save me time let me know!