Hi JK
Max is a rate-adaptive service, iow, it will try and go as fast as your line can support. The single most critical factor in that is your downstream attenuation, which for you is 39db. At that level, I'd expect you to be achieving a sync speed of 5-6000kbps. The other factor though is the quality of the line and its susceptibility to noise, and that's much harder to quantify. I sync at around 3500 on a 56db attenuation. My neighbours sync at between 512k and 2000k, the attenuation figures are similar within +/-2db.
Normally, BT give you a target noise margin of 6db, and run the line as fast as possible with the margin. In your case, it looks like the dynamic line management software has found your line unstable at that speed and so increased the target margin to 9db. That will cost you about 500k of sync speed.
A shielded ADSL cable (RJ11-RJ11) may help, but the reason I suggested borrowing another router is that different makes work better with different lines, with a possible speed difference of 1000kbps or so. It also eliminates any possible fault with the router.
As Simon has said, you shouldn't have to re-train with a like-for-like migration. There is no fixed-rate 4Mbps service though, the fastest fixed rate product is 2Mbps.
You're very welcome to join IDNetters, as is everyone, but I'll always try to answer any questions here. Obviously, though I spend most of my time over there.
HTH