Just set up a PPTP tunnel, it connects and works for traffic such as email (POP), but as soon as I try to use Remote Desktop from a windows box behind the NAT/PPTP/etc router I get this error in my log:
After this no traffic will pass on the interface at all and I need to reconnect.

I did not find reference to this anywhere here or otherwise. I did find reference to a four-byte difference which setting MTUs properly would fix, but mine is only off by one byte somehow.

I've set my mtu to 1204 in my tunnel scripts (using Gentoo-native methods and /etc/ppp/options.<tunnelname> with /etc/ppp/peers/<tunnelname>) and then tried setting the MTU on both the interface and my routing entry to less (tried 1200, 1000, 800) but still nothing. I was hoping to get RDP packets to fragment and thus stay well under the pppd MTU but it seems no matter what I still get the above error regardless.

Using kernel 2.6.15-gentoo-r1 and pppd 2.4.2, and my ppp_mppe module says it's Frank Cusack's one (I think thats the one I want).

Set the MTU higher.
It can be as high as 1450..