This sounds not like any issue with your mesh, but instead a problem with your mesh having a collision box. You cannot place a player start inside a collision box otherwise it will give this error.
You will want to do a couple of things to resolve this. You will want to break the mesh apart into modular pieces with their own collision, setup custom collision in your 3Ds Max, use UE4’s collision generation and place the collision boxes accordingly, or use blocking volumes.
That was exactly it. I had walls imported on all sides, so when I was trying to create a playerstart in the middle, I was just in a massive collision box!
I think blocking volumes will be the way to go without tampering with the mesh too much.