/sbin/cryptsetup not found on boot

I've created an encrypted root partition using LUKS which contains a few LVM partitions. I can't boot and get the following output on startup:

Begin mounting root file system ... Begin: Running /scripts/local-top ... /scripts/local-top/cryptroot: line 1: /sbin/cryptsetup: not found

It still prompts me for the password:

Unlocking the disk /dev/sda5 (macbookcrypt)
Enter passphrase: *******************************
cryptsetup: cryptesetup failed, bad password or options?
/scripts/local-top/cryptroot: line 1: /sbin/cryptsetup: not found

Yet it fails every time.

My boot command-line is:

vmlinuz-3.13.0-37 generic ro root=/dev/mapper/macbooklvm-root cryptopts=target=macbookcrypt,source=/dev/sda5,lvm=macbooklvm recovery initrd=\initrd.img-3.13.0-37-generic

I've added "dm_crypt" to /etc/modules and then did update-initramfs to regenerate with dm_crypt included. I'm on Ubuntu 14.04 by the way.

In the initramfs shell, I can't seem to locate cryptsetup anywhere:

(initramfs) cat /proc/modules | grep crypt
dm_crypt 23177 0 - Live 0xffffffffa0006000
(initramfs) find / -iname "cryptsetup"
(initramfs)

It appears that the dm_crypt module is loaded', so that's good, but cryptsetup isn't present here. How do I install it to my Linux boot? Does it need to be included in initrd, vmlinuz, or System files somehow? I'm new to this hackery.