I think I found solution – proper binary parser must be selected so Eclipse can recognize the executable:
Select the project, then right-click. Project->Properties->C/C++ Build->Settings->Binary Parsers, PE Windows Parser.
I.e. if Cygwin compiler is used then Cygwin parser should be used.
That worked for me at least for Cross-compiler (both on Windows 7 and Ubuntu 12.04). On Linux, I use Elf parser.
If anyone has the better solution, please advise.