Thanks for the reply.
Are there any other cases than large textures that could cause this? It happened on two games, in one game we set the max texture size to 2k and it worked, in the other it didn't. And, this only happens when we're building from Unity 5.3.4 and beyond, anything below that everything works fine, even if the max atlas texture size was 4k! Any idea what's going on there?