Pues con Ubuntu la verdad que no sé cómo irá, pero con Gentoo (y supongo que con todas las distros de forma similar), es cargar el LiveCD, meterte en tu partición linux y reinstalar grub en el MBR (ó hacer cambios en el fichero de configuración para que te de a escoger Windows y luego grabar en el MBR de nuevo, da lo mismo).
Seguramente Ubuntu tenga algo en plan sencillito sencillito, pero ya te digo, supongo que será metiendo el CD y rebuscando por ahí como volver a grabar grub en el el MBR (grub-install desde consola). Tan sólo eso.
Salu2!