Problem solved. Exchanged for an HP Photosmart C6380. The scans are acceptable now, I can live with them as is if I'm just printing same size copies. If I really want them to look good I can clone out a few dust speckles here and there. But nothing as bad as the scanlines the Kodak was getting. When I took it back to Best Buy I told them to send it back to the vendor and not to resell as open item because it'll just keep coming back returned if they do.
Before I made up my mind to exchange it, I tried it on a PC too, and even 4 different prints developed at various places around town, from various times within the last 5 years and the scans were all shit.
I've uploaded scans of two of the same pictures on Flickr (same link as above) so you can see the same photo scanned on the same computer, into the same program, with two different scanners.