It's probably some issue with your PATH. What do you get when run:
which ruby
which gem
echo $PATH
Thanks,
Pedro
Sorry, can you also let me know what do you see when you run: gem env ?
In this case, can you run it like:
/var/lib/gems/1.8/bin/kensa ?
If so, you just need to add that location to your PATH.