I know this response to this post is very late in the game, but I am mostly responding to this because I recently had the same problem with no idea what was going on, and for anyone in the future who has the same trouble starting out in Maya. and yahoo/googles it and only this comes up. Here it is. The valency of the vertices can be raised or lowered as follows:
Go to Modify>Convert>Polygons to Subdiv and select the little square for the option box. The valency can be raised by selecting either the slider bar or the text box of "Maximum Edges Per Vertex" option. 32 is the defualt, but if the valence limit is too low, raise this up higher. The max level it can go is 50 it seems, so if you go that high and still are exceeding the valence limit, consider a few options. 1) Try to go to the modeling menu (Shortcut is F3 to switch to it, or select from drop down box) and then go to Polygons>Cleanup. You can select the option on what to clean up but I admit that I don't know much about that option. 2) Try to see if you can break up your polygon a bit. If it was one whole polygon and its over the max limit of valency then good lord. If it was polygons you combined together into one through the Polygon>Combine functionality, then try to undo that combine, convert to subdivs, then combine things later. This may produce undesirable results, but you can manipulate them back to the desired level of detail later if you like. This is simply to get them into subdiv mode.
I hope this helps, and for the two who originally posted, sorry that I came along in the game so late.
Good Modelin!