updatedb rebuilds the database used by 'locate' , whereas 'which' searches
through the path.
So either your PATH doesn't include /usr/bin (echo $PATH to check), or
you really don't have ruby there. If this is the case then either you are
using the wrong template or you started the qube before the template had
fully shut down. (Or the Qubes template implementation is broken.)
You shouldn't need to do anything additional for a template based qube.
Check you are using the template you think - qvm-prefs <name>
template.
Check in the template again.
Restart the qube when the template is fully shut down.
Test again.