Most likely this is a problem with TeamCity not finding the path to ruby executables.
You can address this by overriding the value to the PATH environment variable in your build configuration in the Build Parameters section.
env.PATH=/path/to/ruby;%env.PATH%
See this answer for the proper links to documentation, etc.
EDIT #1
I noticed when updating one of my configurations that TeamCity is supposed to take care of appending values so you DO NOT need to set path equal to itself. The post mentioned above is a workaround for a bug where TeamCity was overwriting the values, but that has been corrected. See the help at the mouse-over for more information:

EDIT #2
I tested edit #1 and found that is not the case. You do need to
- create an environment variable
env.Path
- and set it's value to itself plus your new path; in my example,
C:\Program Files\MySQL\MySQL Server 5.6\bin\;%env.Path%
- you do NOT need to say
env.Path=...
as listed above; that is what the configuration file will look like.
I tested this out by doing the following:
- Created a new project with no repository
- Added a command line build step to `echo %env.Path%
- Added a command step to call MySql
mysql --help
This will fail if it cannot find MySql
I then ran it for each of the following settings for the env.Path
variable:
- Not added / changed; TeamCity reports out the environment variable for the build agent as is.
- Added as just
C:\Program Files\MySQL\MySQL Server 5.6\bin\
. TeamCity reports out only that entry.
- Added as
C:\Program Files\MySQL\MySQL Server 5.6\bin\;%env.Path%
. TeamCity prepends C:\Program Files\MySQL\MySQL Server 5.6\bin\
to the build agent's values shown in #1. The result is what we want, #1 + #2