Do you actually have the maps in your baseq3 directory? IOW, can you play those maps in single player mode? Also, what command are you using to invoke quake3? Here is the shell script I use to run q3.
# Needed to make symlinks/shortcuts work.
# the binaries must run with correct working directory
./quake3.x86 +set vm_game 2 + set vm_cgame 2 + set vm_ui 2 $*
Also, have you discovered "xqf"? yet? It's an online game browser/starter similar to All-Seeing-Eye, but for linux.