Windows isn't dictating your ways - in fact, that's part of the problem.
When your system boots, once BIOS has done its thing and worked out how many hard drives you have, where they are, and how to address them (et cetera), it hands off to a tiny portion of the primary boot device called the Master Boot Record (MBR). Inside there, operating systems install small records to tell the computer what to do next to start up.
By simply removing Windows from the back end of that, your MBR doesn't make sense to the computer any more, since it's referencing files which don't exist. If you want to dual-boot, you should always install Windows first for this reason. Microsoft's bootloader will load multiple versions of Windows very nicely, but traditionally isn't that happy with other operating systems.
The common bootloaders for linux systems are GRUB and LILO. One is probably installed for you automatically if you installed linux from a DVD or similar. It's just that it gets overwritten when Windows installs its own bootloader in the MBR. Unlike the Windows loader, though, GRUB will boot Windows too, and so will LILO.
There are a few ways to fix your linux install, some already mentioned. I'd personally use a liveCD linux install to boot up, mount your devices, chroot into your linux environment, and run grub-install to get it back into the MBR and make your system boot again.