Ti, the Denon 3312 would be a fine choice and the best buy on it would be the the factory refurb unit from Accessories4less which Alex mentioned and is specifically shown here
for about $600 with shipping included. These factory refurbished units should be at least as reliable as brand-new ones.
Speakers rated at 4 ohms don't necessarily use more power. Power consumption at a given loudness level depends on speaker sensitivity, not impedance rating. Many speakers rated at 4 ohms(e.g., Axiom M80s)are more sensitive than some smaller speakers rated at 8 ohms and actually need less power. The 3312 has more maximum power capacity than your present receiver and should drive your speakers with ease.