The ultimate answer depends on the structural margins used in the construction of the first stage. It's possible that it was overdesigned with this switch in mind, in which case you could simply replace the engines.
If not, as osgx points out, the RD-180 is throttleable, so it could simply be throttled down to 76% to reach 660 klbf. At it's lowest range, however, (47%) the thrust is 404 klbf, but the NK-33 is only throttleable down to 55% , which translates to 363 klbf from two of them.
The reason that's important is because it says here  that the Antares does throttle down towards the end of the flight to maintain structural limits on the rocket. However, it's unclear how far it throttles down. If it only throttled down to 61%, that matches the lower end of the RD-180, so a structural redesign of the first stage would not be necessary.
Even if it required a structural redesign of the rocket, it might still be a reasonable replacement because, as you note, the engine is no longer in production. If they kept using it, they would have to pay to restart the production line, which could be a lot more costly than a structural redesign of the rocket. The RD-180 is in production for the Atlas V, as you also mentioned.
Another question is gimbaling, which is the process of moving the nozzles slightly in order to correct the course of the rocket. This isn't really a problem, since the NK-33 can gimbal up to 6 degrees , and the each of the RD-180's nozzles can gimbal up to 8 degrees . As osgx noted, a single RD-180 has two nozzles, and each NK-33 has one, so the nozzle count is fine. If the RD-180 had more limits on its gimbaling, Orbital would need a new solution for steering the rocket on its way up.
In any case, Orbital has time to come up with a solution. They purchased enough engines to complete their obligations to NASA under their Commercial Resupply Services agreement , and to date no one else has signed up to use the Antares for their payload