I had this problem too - Mac OS Server X 10.4.11, Leopard 10.5.1 client machines. I did a bit of googling around and finally fixed it by creating a patched pppd file for the OS X server. Below the sources of the info I collected:
* More info about the error: this seems to be relevant:
http://pptpclient.sourceforge.net/howto-diagnosis.phtml#mppe_rbp
* The Source code to Darwin (which underlies Mac OS X):
http://www.opensource.apple.com/darwinsource/
I fetched the pppd source code from the Mac OS X 10.4.11 section; downloaded the .tar.gz file for ppp-233.18
You might need to be registered with Apple to get access to the source code. I am a developer, so I got access, but I don't know how/if it works for non-developers.
Once I had the source code downloaded and expanded to my computer, I patched the file Helpers/pppd/ccp.c and disabled the 'if' statement spread over 4 lines around line 996. This is a total hack - I have a vague idea what I am doing, but I did not study the source closely - so let's say I got lucky. (Actually, it's more of an educated guess).
Then I recompiled just the pppd tool target (deployment configuration) using Xcode 3.0, and then replaced the old pppd on my Mac OS X server. With the newly compiled pppd copied in my admin user's home directory, this was the sequence I executed on the Mac OS X server
<login as an admin user>
<start Terminal command-line tool>
sudo bash
<enter your password>
mv /usr/sbin/pppd /usr/sbin/pppd.original
chmod 4511 pppd
chown root:wheel pppd
mv pppd /usr/sbin/pppd
Ctrl-D
Quit terminal
And from then on, my L2TP connection started working! No more "MPPE required but peer negotiation failed" in my logs etc...
I know that this is probably totally unhelpful for many people who don't have development experience, but I am not sure what the legalities are of distributing a patched pppd. Furthermore, I am not prepared to take any responsibility - this is really mucking around deep in the system, so if you do like I did, you're on your own; if things go awry, there's no one to blame but yourself.
If someone at Apple is reading this and can shed some light on what the legalities are, I might be able to make the patched pppd available (without any warranties whatsoever).