A solução para este erro foi (e é para todos esses erros) dar uma olhada no arquivo mkmf.log (para mim, /cygdrive/d/d/Documents/.gem/ruby/extensions/x86_64-cygwin/ffi-1.9.8/mkmf.log ) e ver quais bibliotecas estão faltando.
No meu caso, -lcrypt e -lgmp estavam falhando, então eu tive que "cygwin-setup" libcrypt-devel e libgmp-devel .