Ok, I've narrowed it down to just being a bug. A really big bug.
To recap, I'm trying to move a scene from Maya 2011, to Max 2009. I installed Max 2011 to also test, and there were some differences no matter what version I set the FBX to export.
Going Maya 2011 to Max 2011, it worked fine. I had to go into my Object Properties and turn on Vertex Channel Display and set it to be Shaded. Once I did this, my vertex colour information displayed. However, going from Max 2011 to Max 2009 hasn't been so easy and it's the package I need to be in.
In Max 2009 when I export via FBX from Max 2011 I'm able to keep my vertex colour information but I lose my UV's. When I export via OBJ, I keep the UV's but lose vertex colour information (being it's not supported). I'm ready to just import via OBJ and just re-do my vertex painting. I can't keep trouble shooting this situation. I don't have time, but I would really love to know what the hell is causing this.
My Hypothesis, FBX sucks.