In the worst case those codes can mean that the cat itself has gone bad, but as many people have opined across the internet; if you maintain your vehicle a modern cat should last the majority, if not all, of the life of the vehicle.
More common (and cheaper) problems that can throw those codes are:
-a leak in the exhaust system; sometimes this isn't even the metal exhaust components but the seal between the cat and tubing that has failed and is leaking.
-a bad or failing O2 sensor or related wiring
If in fact the cats were dying from poisoning or meltdown because of an engine problem it isn't too far fetched that they would fail in the relatively same time-frame.
Also, it may be a typo in your original post, but you said you initially had a Bank 1 cat replaced because of a p0430 and now are getting a p0431. If those codes are indeed correct and they replaced a Bank 1 cat, they did it wrong.
Both of those codes are for Bank 2 - a p0430 is "Catalyst System Efficiency Below Threshold (Bank 2)" and a p0431 is "Warm Up Catalyst Efficiency Below Threshold (Bank 2)". If they did indeed replace the wrong cat you could be getting the code for the same problem that originally threw it.