The image you posted is not 8-bit (indexed colour) but 24-bit. That is, 8 bits each for Red, Green and Blue. You won't get any benefit from going to 16-bits per colour.
The problem is as Jellby said -
moire patterns from the poor resizing algortihm. Looking at the image you posted, that doesn't look like a scan of an actual print from an engraving, but a
halftone image of an engraving.
The way I'd handle it would be to apply some guassian blur to rmeove the halftoning, and then apply just a little unsharp mask, barely enough to be noticeable at 200%.
And doing that gets the image I attach, which should look pretty good, even in ADE.
[now uploaded as a jpg full size]