Installing command-t is fairly easy on windows. Just compile as instructed with latest ruby 1.9 + devkit and replace gvim.exe with the one specified in this page https://wincent.com/comments/6544.
I can't speak for other vim users, but I haven't had a lot of luck with distro versions of vim and Ruby/Python extension scripts on Linux either. After fighting with it for a while, I ended up just declaring my .vimrc to be a VimScript-only zone. It sucks losing Gundo and Command-T and a couple other great plugins, but it's done wonders for my sanity, and everything works well on Windows as a bonus.
I also had no problem installing it in Ubuntu/Mint. Just removed vanilla vim and installed vim-gtk and then compiled command-t.
Command-t is actually my only non-vimscript plugin in my plugin list, and it is rightfully so :). I tried to cope with CtrlP, but it feels too slow for me for large collection of files. Also its fuzzy matching is not on par with command-t. I have actually no problem to take this little hassle to install command-t for performance consideration :).