Just an update on where I am with regards to adding a card to the app store.
In a vague last ditch attempt to get something working, I did a wipe of my Touchpad (erase apps and data) and made a new profile with a different email address. I entered the card details again, but this time the error code changed from LOC02029 to PMTxxxx (cant remember the exact code - sorry) however it still wouldn't let me add the card.
Now the interesting part is that I changed the billing country to Ireland, entered the details again, and it accepted the card first time. I live in England with an English address, so have no idea why this would work, but it has.
So it may be worth at least trying to add the card using Ireland as the billing country and see if it makes a difference to anybody having trouble. Bear in mind if you do go down the 'Erase Apps & Data' route, you will have to set up your Touchpad again. Also if you have any patches installed you need to clear them first (I didn't, and it was a bit of a pain to sort!).
Note this was with my prepaid Visa card, not my Halifax debit card I originally tried. I haven't tried adding the Halifax card since I got this one working, so I have no idea if this would work with that. To be honest I don't want to try, as my card ended up being blocked by the bank due to all the failed attempts trying to add it to the app catalogue first time round!
Hope this helps someone.