I built the tools on Linux, as you knew.
I didn't try it on Widnows, but the patch can be easily adapted.
I am not sure if sym-link works on cygwin?
Maybe some one can try out.
One minor issue in my first post, the crt1.o is for the lastest uClbc snapshot.
It should be spelled as crt0.o for your case.
If you follow marc's site to build toolschain, it is even more simple to do the job.
The nios2-elf-gcc should be spelled as nios2-linux-uClibc-gcc.
And -nostdinc incdirs and -nostdlib crt0.o libs libdirs can be omited, because they are compiled into uClibc default.