What is the difference between "not recommended" and "rejected" as outcome of a graduate program application? I was recently told I wasnt "recommended" into a graduate program and was given a referral to another program. 

What exactly would it means to not get "recommended" as apposed to being rejected? And is being referred to another program a common practice?
At many US universities, the department you apply to makes "recommendations" to the graduate school. Getting the recommendation from the department is usually the hard part -- that's where they review your grades, letters, essays, etc. The recommendations (accept/wait-list/reject) are then forwarded to the graduate school. 

It is normally the graduate school that sends the rejection letter. For non-rejected students, the grad school will go through the applications again just to make sure you meet their requirements for admission (you are highly unlikely to get this far if you don't -- but something like unreported academic misconduct might be caught at this stage). If all checks out, they will approve you, and either the school or your department will send your offer letter.

My guess is that it's the department (or someone in the department) that told you that you were "not recommended." Technically, only the graduate school can formally reject you and close your application -- but the odds that the grad school will reverse the decision in this direction is near zero.