This is pretty easy. Partition your disk, install Windows and Ubuntu. Use TrueCrypt on the Windows partition, which will encrypt Windows but leave Ubuntu unencrypted.
You'll then find you can probably only boot into Windows, and then through the TrueCrypt bootloader. Sounds like you're there already.
Say your disk is sda, with Windows on sda1 and Linux on sda2 (this is hypothetical, yours looks like it won't be sda2). TrueCrypt will install onto the MBR on sda and overwrite GRUB.
Use the Ubuntu distro CD to boot up a live CD, then chroot into your pre-installed system. Like so:
sudo su -
mkdir -p /mnt/ubuntu
mount /dev/sda2 /mnt/ubuntu
mount --bind /proc /mnt/ubuntu/proc
mount --bind /dev /mnt/ubuntu/dev
chroot /mnt/ubuntu
Then install the GRUB bootloader, but to sda2, rather than sda.
grub-install /dev/sda2 --force
Then, when you reboot, you'll still get the TrueCrypt loader asking you for a password to boot from sda -> sda1 into Windows. But when you press ESCAPE you'll get the option to bypass and boot straight into Linux, but from sda2 rather than the MBR.
But wait
Before you do this, one caveat: if you get your grub-install wrong, and overwrite the sda MBR, or if you do a kernel upgrade which triggers GRUB to overwrite the MBR, you'll find you need to reinstall the TrueCrypt bootloader in order to get back into Windows. This is a massive hassle if you're not prepared.
I'd suggest that before you fiddle with GRUB, you back up the TrueCrypt bootloader stuff from within Linux. That way, when you break TrueCrypt and can only get into Linux, you can easily write it back.
Back up your TrueCrypt boot loader:
dd if=/dev/sda of=~/truecrypt.mbr count=1 bs=512
dd if=/dev/sda of=~/truecrypt.backup count=8 bs=32256 # Just in case
Restore your TrueCrypt boot loader (I call this restore-truecrypt.sh):
sudo dd if=~/truecrypt.mbr of=/dev/sda count=1 bs=512
sudo dd if=~/truecrypt.backup of=/dev/sda count=8 bs=32256
sudo grub-install /dev/sda2 --force
I have both of these sets of commands in little shell scripts, which I keep handy. When I accidentially zap my bootloader (it happens) I don't want to be Googling around for the commands or reading man.
Oh, and a word on compatibility. When I write "GRUB", I meant GRUB 1 or 2. Personally, I do it with GRUB 2 on 10.04 and Windows 7... but it worked fine with older versions of GRUB, Windows and Linux.
Best Answer
Did a quick google search and it looks like the default key for BIOS access if F2, not F12. If you tried that one, like Frank said, you're probably just not hitting it in time. Try spamming the bios key while turning the machine on if you're still having trouble.