Sicuro che tu l'abbia installato?

Comunque il locate non trova nulla se prima non aggiorni il db con "updatedb"...
Controlla che /etc/X11 o /usr/X11R6 esista...
E poi startx prova a cercarlo in:
/usr/X11R6/bin/startx