Do you have the UV lines being displayed in your painted texture? Does your painted texture overlap your UV shells by at least a few pixels?