Hi Roy,
It looks like your TeamCity setup is using Ubuntu Trusty to perform
the build. Travis CI is using Ubuntu Precise instead[0]. The
mingw-w64-dev package is only available in Precise[1]. It looks like
that package was split into mingw-w64-x86-64-dev and
mingw-w64-i686-dev, so those are what have to be used with Ubuntu
Trusty.
[0] - http://docs.travis-ci.com/user/ci-environment/
[1] - http://packages.ubuntu.com/precise/mingw-w64-dev
[2] - http://packages.ubuntu.com/trusty/mingw-w64-x86-64-dev
[3] - http://packages.ubuntu.com/trusty/mingw-w64-i686-dev
Cheers,
Joseph