I literally poked that patch into debian/patches{/series}, quilt applied it and rebuilt, and it started working for me. Maybe there's something different about our configs?
Strange, that patch seems to slightly change how the hardcoded dh params are loaded, but it doesn't seem to change the size of them or anything.
It seems that more recently commit 6b3844987509517dad6e41391d9142b867266b8b ripped out the hardcoded dh parameters and replaced them with a system for loading them from files, but that seems too intrusive for a stable update. I am just taking a flyby look at rc bugs, but if this was my package I would propose a patch replacing the hardcoded 1024 bit parameters with hardcoded 4096 bit parameters as a minimally intrusive fix for stable.