IPSec VPN between Amazon VPC and Linux Server

Well, I cheated :) I installed Astaro gateway which is officially supported by Amazon and then used that to model my own. You can just SSH into the Astaro unit and see how they set everything up. Of course, you could stick with the Astaro unit if you feel like paying for it.

Figured it out. Had to change my ipsec-tools.conf to this:

flush;
spdflush;

# Generic routing
spdadd 10.4.0.0/16 10.3.0.0/25 any -P in  ipsec esp/tunnel/205.251.233.121-199.167.xxx.xxx/require;
spdadd 10.3.0.0/25 10.4.0.0/16 any -P out ipsec esp/tunnel/199.167.xxx.xxx-205.251.233.121/require;

# Tunnel 1
spdadd 169.254.249.1/30 169.254.249.2/30 any -P in  ipsec esp/tunnel/205.251.233.121-199.167.xxx.xxx/require;
spdadd 169.254.249.2/30 169.254.249.1/30 any -P out ipsec esp/tunnel/199.167.xxx.xxx-205.251.233.121/require;

spdadd 10.4.0.0/16 169.254.249.2/30 any -P in  ipsec esp/tunnel/205.251.233.121-199.167.xxx.xxx/require;
spdadd 169.254.249.2/30 10.4.0.0/16 any -P out ipsec esp/tunnel/199.167.xxx.xxx-205.251.233.121/require;

# Tunnel 2
spdadd 169.254.249.5/30 169.254.249.6/30 any -P in  ipsec esp/tunnel/205.251.233.122-199.167.xxx.xxx/require;
spdadd 169.254.249.6/30 169.254.249.5/30 any -P out ipsec esp/tunnel/199.167.xxx.xxx-205.251.233.122/require;

spdadd 10.4.0.0/16 169.254.249.6/30 any -P in  ipsec esp/tunnel/205.251.233.122-199.167.xxx.xxx/require;
spdadd 169.254.249.6/30 10.4.0.0/16 any -P out ipsec esp/tunnel/199.167.xxx.xxx-205.251.233.122/require;

And change my racoon.conf to this:

path pre_shared_key "/etc/racoon/psk.txt";

remote 205.251.233.122 {
        exchange_mode main;
        lifetime time 28800 seconds;
        proposal {
                encryption_algorithm aes128;
                hash_algorithm sha1;
                authentication_method pre_shared_key;
                dh_group 2;
        }
        generate_policy off;
}

remote 205.251.233.121 {
        exchange_mode main;
        lifetime time 28800 seconds;
        proposal {
                encryption_algorithm aes128;
                hash_algorithm sha1;
                authentication_method pre_shared_key;
                dh_group 2;
        }
        generate_policy off;
}

sainfo address 169.254.249.2/30 any address 169.254.249.1/30 any {
    pfs_group 2;
    lifetime time 3600 seconds;
    encryption_algorithm aes128;
    authentication_algorithm hmac_sha1;
    compression_algorithm deflate;
}

sainfo address 169.254.249.6/30 any address 169.254.249.5/30 any {
    pfs_group 2;
    lifetime time 3600 seconds;
    encryption_algorithm aes128;
    authentication_algorithm hmac_sha1;
    compression_algorithm deflate;
}

sainfo address 10.3.0.0/25 any address 10.4.0.0/16 any {
    pfs_group 2;
    lifetime time 3600 seconds;
    encryption_algorithm aes128;
    authentication_algorithm hmac_sha1;
    compression_algorithm deflate;
}

However, this configuration as I understand it will only route traffic between 10.3.0.0/25 and 10.4.0.0/16 over the first tunnel (via x.x.x.121). I'll update the answer when I figure that out.