I am and international student from Greece. Up until May 2008 I was doing my OPT under an F1 visa after I completed my Master's here in the US. Now I have to move from Ohio to Arizona to start my PhD. Are the relocation expenses in this case tax deductible or not?

No, in this case the expenses are not dedutible.
Only the moving expenses to move to start a new job are deductible, if requirements are met.