Hi,
I tried to use the atlas texture with GUITexture as you suggested and did not have the edges.
We made a bit more tests on different devices and we found that every devices (all nexus 4) that had this problem had a modified version of android in some way, on another device with an original non modified version of android, the problem did not appear. We could only test on one device with an original version of android then i can't confirm but this may be kind of related.
Concerning the texture settings, mip maps has been desabled for every one and filtering is set to bilinear. The compression is set to automatic compressed which becomes 16bits texture in unity android.
Here is a photo of the problem. I tried to get a screenshot directly on device but interestingly, the grabbed image did not have the problem...
Thanks for your help.