Ok,
Was the 856L in the DMZ on the 855?
Did you change the WAN port speed on the new routers from Auto to say 10, then 100? What does your ISP support for the WAN port speed? Do you know. It's been 100 for a while and most new ISP Modems support 1000Mb so over here, I manually set the routers for 1000Mb.
Ok, seems like you have done some foot work here. Then the only other thing to test would be a ISP Stand alone modem at a different location. I presume and hope this will have positive results and presume it will probably point to the direction of there is a issue between your ISP service and this new gen routers.
I think after you can test at a different location, and what ever the results are, a phone support is going to be needed with DLink, ask for level 3 or higher support. Nothing level 1 or 2 can really do here. You, and information here in the forums have already covered that. If these routers work with a standard ISP stand alone modem, I really feel there is a problem between the ISP service and these routers. I would presume that maybe something on the ISP side could be at fault since it's older HW being used, however it would point also to the FW on these new gen routers possibly not handling what ever the older HW connection are using.