Call recording works on most, if not on all phones, you just need to find the right application that uses the phone's system properly.
Check this, similar thread, I suggested two applications that you can try
http://xdaforums.com/showpost.php?p=49953280&postcount=3