Okay it kept saying I had to raise the UV Map size or lower the UV map border. It worked with a uv map border of 2 and a uv map size of a wopping 8192 :/. Anyway it's looked as though it's worked, the only problem is there's no option to export the texture? Edit: Oh wait got it.
Aha, I see what you're doing now. Delete the UVs, set the UV border to a higher (try 2), and then recreate the AUVs. Do a new texture from polypaint and it should be fine. Explanation: The UV border acts like padding around the UV shells. If you set it to 0 it is going to cram them together in a way that it will put UV…
Odd that the default value was 4 and not 2. But even a value of 1 should work fine (and allow for a smaller texture res). You might even get away with using a uv border of 0 if you'd export the tool, import into max, quickly scale the UV's a tad bit so nothing touches the 0 or 1 border, and the load those UVs back into…