I found two great articles that helped guide me through the process of setting up a VPN that connected through my AWS instance. One, entitled Setting up a VPN-server on Amazon EC2 was specific to my install (it seemed) of Linux 11.04, while the other tutorial Create a Personal VPN Server on the Amazon Cloud came with a solid YouTube video walkthrough.
Having gone through those posts in detail, I wanted to outline my exact process as there were a few differences.
First off, the linux OS I'm running is 11.04 Natty Narwhal. I'm running this in a LAMP stack, but that should be pretty independent for your respective flow. It's a micro instance on AWS, and doesn't have any fancy applications installed on it. Here's the code:
sudo apt-get -y install pptpd
sudo vi /etc/ppp/chap-secrets
The first installs the pptpd application, while the second one opens up the credentials file for you to create users. A sample line you should add would look as follows:
<username> pptpd <password> *
The asterisk simply allows the VPN to be accessed by all IP addresses.
sudo vi /etc/sysctl.conf
In this file, we simple need to uncomment the line net.ipv4.ip_forward=1
sudo sysctl -p
This reloads the configuration file we just edited.
sudo iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
This (I think) customizes your system's firewall to allow connections to come in and be routed properly.
sudo vi /etc/rc.local
In this file, we want to add the above iptables rule again (minus the sudo):
iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
And finally, let's reboot the VPN and system:
sudo /etc/init.d/pptpd restart
sudo reboot
I made the assumption that that would be it, but alas, I needed to open up port 1723 in my instances security group/firewall under the TCP protocol. After having done that, it definitely should have worked. And it did when I tethered my system through my iPhone's 3G connection. VPN was glorious. I had my instance's IP while surfing. Hello Hulu & Netflix.
So in a way, it was successful, but alas, I couldn't connect via my Linksys router. When I find a way around this, I'll update the most. I have a feeling I simply need to open up the same port on my router.
Update
Thus, we have it. Simply had to open up port 1723 in my router's configuration, and was good to go. The tutorial How to Port Forward/Open Ports on a Linksys Router worked perfectly.
Follow Up (Sep. 24)
The reason it wasn't working from my computer, but was from my phone, wasn't the port on my EC2 instance (which does need to be opened). Rather, it was that my OSX needed to be restarted after a VPN was set up.
Sounds obvious, but just now discovered that while trying to set a new one up :)