Hi Toby,
We have two brick walls in the back garden as well, we were thinking of painting them first and putting trellis up, but I think now we're going to buy lengths of fence that you can get from Homebase or B&Q or wherever and then put trellis onto that. The fence will hide the walls and then the trellis will allow the plants to grow up the fence....
M