I found in my PC a GDB installed with Visual Studio named "i686-linux-gnu-gdb.exe".
I think my problem was trying to access "localhost". The program I am trying to debug is certainly NOT in my local machine!
In the remote, when I start the program under gdbserver, the last line it shows (waiting for the gdb client to connect) is:
Listening on port 2159
I put this number in the "Port" box under "Connect via socket" in the "Attach debugger" window that opens when you start a remote debug session with GDB and the program started running (after I clicked on the "play" button after waiting for a long time for a "starting debugging" message)!
A final warning for those trying to do what I was. If you receive a message like
Error starting debugger: GDB returned an error opening the executable
"w:\dir2\dir1\program": not in executable format
It may mean that what you thought was the program you want to debug is, in fact, a script to call it! As you can imagine, it just happened to me.
After I drilled down into the script and found the actual program, everything is working!
Linux utility "file" is your friend! (it shows / tries to guess the type of a file, e.g. text, script, executable, directory, etc)
Thanks for the help!