Went into an O2 store to get it exchanged, he admitted I was the first. All of their replacements had the same problem so I guess it is a batch issue. Although their display model did not.
I then went to another store (again, display model was perfect), this O2 had a replacement which wasn't 100% smooth but was a huge improvement over my 1-2mm raised edge. The new one is again raised on the right hand-side, but only 0.5mm or so. I can live with that. They were happy to replace it as they said they had to do it a lot with the original 3G.
So, there are good ones out there! Call me fussy, but I'm the one that's paying.