Before taking a look at your old amp specs, having two terminals does not always mean it is 2 channel. Some monoblock amps come with two terminals to make it easier for you to install two subwoofers, but internally the channels are bridged so it doesn't matter if you use one set or two, the load is the same.
Now... when you put all the negative wires together and all the positive wires together, that means you're wiring in parallel (as opposed to series where the positive from one sub goes to the negative of the other sub and then the remaining pos and neg wires go to the amp to form a daisy chain). That kind of setup will halve the load, so two 4 ohm drivers will create an 8 ohm load, which reduces power output of the amplifier but can allow the amp to run cooler and sound relatively cleaner.
The subs are rated at 300w each and have a resistance of 4 ohms each. So, the way you had them wired yielded a 2ohm load on the amplifier. This is typical of most monoblock subwoofer setups. Basically any 2ohm capable class D monoblock amp with 600w or so should work out for you.
I'll suggest some if I think of any, but that should get the ball rolling.

Price of course is a factor...