First I start out by scanning in and cropping the image, like so:

(as a sidenote, I do get the same results with an unleveled image)
Then I go about doing my thing and level it..

And hit a roadblock when I try to resize.

(bicubic)

(billinear)
I can only assume that I'm going wrong somewhere along the way. Does anyone have any advice or know of a good way to resize and still come out with crisp (or at least clear) lines?