If you want to see how 'autolevels' works try using 'levels' yourself and play around. You'll get much better results not using any of the 'auto' functions.
Basically autolevels looks for the darkest and lightest parts of your photo and re-maps these to Black and White. This often has the effect of improving contrast AND Removing colour casts, but as you have found it can sometimes introduce them. Try using Levels and select the eyedropper tools within levels to set you own black and white points by clicking on your photo till they look right. This is often a good basic way to start correcting colour and contrast in PS