Thanks for the advice everyone. Thought I would post an update.
I've cut down the climbing to once a week and started going to the gym 2 - 3 times a week and as well as running, doing oppositional stuff, triceps dips, dumbell presses, shoulder presses and eccentric bicep curls with a low weight...then icing when I get home.
I also bought a book on stretching and have found it useful for stretching my arms and shoulders (the exercises in it, not the book itself).
There seems to have been a small improvement but not as much as I would have hoped for - it's taking a long time to get better! I guess some progress is better than none though.
At least the nights a drawing in now, so I'm not tempted to climb lots of crimpy stuff outdoors which seems to really aggravate things. :-)