2008-08-08 に解決策が書いてある。
cmd.exeでashを立ち上げる
>cd \cygwin\bin
↓
C:\cygwin\bin>ash
立ち上がったシェル上で rebaseall を実行
cygwinのシェルから立ち上げた ash では実行出来ないので注意。
↓
$ /bin/rebaseall
cygwinのサービスが立ち上がっているとエラーメッセージが出力されて動作が中断してしまう。
ところで、最新のcygwinを新規インストールすると、/usr/X11R6/bin/startx が含まれていないんだが、別途インストールするようになったんだろうか。。。