After two tries at different times and many days this time, researching, and trying again, I have found out how to get a VPN server running on Ubuntu Server 10.04 behind a NAT router using Pre-Shared Keys.  First of all, 99% of the instructions here, will get you started.  There is one change that took me some looking into to figure out--the openswan package distributed with Ubuntu Server (as of this writing was 1:2.6.23+dfsg-1ubuntu1) will not work if you use it behind a NAT router (or even if only the client will be behind a NAT router--but untested).  To get a version that worked (with all the configuration and stuff from the aforementioned HOWTO and below), I installed openswan from Openswan testing team's PPA (instructions at that link on how to install / use the PPA).  This immediately worked for me once I installed a version >2.6.24.  I should also mention that I personally had some confusion on the IP addresses used. Let me point out slight differences in config files from the HOWTO:

• In /etc/ipsec.conf, add the line "include /etc/ipsec.d/l2tp-psk.conf".
• In /etc/ipsec.d/l2tp-psk.conf (copied from /etc/ipsec.d/examples/l2tp-psk.conf), set left=%defaultroute and leftnexthop=%defaultroute (but may work using server's and gateway IPs, respectively-I had already changed it before stumbling on the openswan binary being the problem).  Change this in both the L2TP-PSK-noNAT and passthrough-for-non-l2tp connections.
• In xl2tpd.conf, under [global] I only had "ipsec saref=yes" enabled. I did not enable listen like the HOWTO, though this might be required if you have more than one NIC / IP in use--can't hurt.
• In xl2tpd.conf under [lns default], set "ip range" to some unused range in your LAN, eg. 192.168.0.100-192.168.0.120.
• In x2ltpd.conf under [lns default] set "local ip" to an unused IP in your LAN, eg. 192.168.0.99.
• In xl2tpd.conf under [lns default] set "require chap=yes", not no.
• In xl2tpd.conf under [lns default] set "name=l2tpd" (not sure it was necessary--I think the change the HOWTO has you do in the options file is the one that matters).
• Copy /etc/ppp/options to /etc/ppp/options.l2tpd.lns, which is included by xl2tpd.conf
• In /etc/ppp/options.l2tpd.lns, add "require-mschap-v2" somewhere on a line by itself.
• In /etc/ppp/options.l2tpd.lns enable both ipcp-accept-local and ipcp-accept-remote.
• In /etc/ppp/options.l2tpd.lns enable ms-dns and set it to the IP of a name server (local, router, ISP or other like OpenDNS). Run "cat /etc/resolv.conf" to find out ones you're using.

I should say that some of the settings above may not strictly be necessary, I'm just saying mine is working doing the things above. I also manually made some changes from command line after running "ipsec verify". I believe the following changes to /etc/sysctl.conf and rebooting will do the same, but I have not rebooted at this time to test. The next time I do, I'll adjust this post. For now, here are the settings to uncomment in /etc/sysctl.conf:

1. net.ipv4.ip_forward (this might not be necessary)
2. net.ipv4.conf.all.accept_redirects (very likely necessary as "ipsec verify" checks for this)
3. net.ipv4.conf.all.send_redirects (very likely necessary as "ipsec verify" checks for this)

 
After following the HOWTO, keeping in mind the changes I've detailed, I was able to get my iPhone setup to connect to the VPN, and further, was able to access both the Intranet and Internet through the VPN (I had "Send all traffic" enabled). I have yet to test any other client, but likely using the settings from the HOWTO will work with Windows clients.  There are other pages at the site the HOWTO is on that have pointers on changes that allow other clients to connect.
 
One last thing. Since your VPN server is behind a NAT router, you need to allow and forward 2 inbound ports: UDP 500 (might not be required) and UDP 4500 (for sure). Since there are many routers out there, that part is left as an exercise for the reader.  I use OpenWRT, and providing those instructions isn't very useful because anyone using that can probably figure out how to add the entries to /etc/firewall.user.
Enjoy your new VPN server!