toddlers
I like your pediatrician's suggestion of switching to Nutramigen. It is a hydrolysate formula, which means the proteins have already been chopped into building blocks so they are easier to digest and pretty impossible to be allergic to. If Nutramigen does not work you will know that formula is not the issue.
Carnation Good Start is another good possibility. It is an example of milk-based formulas not all being the same. The milk proteins in Good Start are partially hydrolyzed, so it may be easier for some kids to digest, but it will not do the trick for a full-blown cow's milk protein allergy.
If the formula is not the issue, there is a long list of rare causes that could be causing the constipation. Hirschprung's disease is probably the most important. This is where there are not enough nerve endings in the end of the colon to push stool out effectively.