ANDROID_HOME not Found

I have been pulling my hair lately, I am running TeamCity for a Build Server, and I have a simple script to kick off an Android Build. The script kicks in and gets stuck on ANDROID_HOME not being able to be found.

This is the message to be exact:
[19:14:47][Step 1/1] [Error: Failed to find ‘ANDROID_HOME’ environment variable. Try setting setting it manually.
[19:14:47][Step 1/1] Failed to find ‘android’ command in your ‘PATH’. Try update your ‘PATH’ to include path to valid SDK directory.]

To most this will look like a n00b type of an issue, and I hoping it is, but I have set all of my ENV Variables manually for all users, including root, and locally it works, and I am able to run my script, but via TeamCity it does not, although the configuration in TeamCity for default ENV for both PATH and ANDROID_HOME are set correctly.

I know that this is most likely a TeamCity issue, and will post a message on their forum, but was thinking if anyone else experienced this, and what was your workaround?

Thanks!