Do the demo files names have uppercase or lowercase letters?
If it's uppercase change it to lower.
An upstream bug that FS can't/won't fix means the linux demoloader
thinks all demos are in all caps.
Solutions:
Make a bash script to rename all demos in the ~/.q3a/q3ut4/demos folder to upper,
or
Use the console to play demos, with /demo DEMONAME
(Remember you can tab-autocomplete!)