Sounds like they didn't give enough padding on the diffuse map. I usually go 8 pixels beyond the edge of the UV island as a buffer to avoid this issue. That should have been done at the time of the texture creation. I fear that your only recourse is to do the thing you've already attempted and paint matching colors along the edges manually.