Since the existing batteries are less than one year old, I wouldn't hesitate to add more batteries of the same type. That would be the least expensive route. I've used the same type of battery, and true deep-cycle or not, they're pretty good for the money.
If you decide to build a new battery array, you might consider adding a switch so that you can connect bank 1, bank 2, or both. That's what I did. It is more work though. I normally have the new bank switched in, and I have to remember to charge the old bank once in awhile. Here's a diagram: http://solarjohn.blogspot.com/2008/05/my-latest-off-grid-pv-system-upgrade.html
