Ah... I've sorted it now...

I think its because i was trying to paint weights on a sub-div.
So instead I've converted my model to a polygon, smoothed it, and now it seems to paint fine.

Cheers.