La grabación de llamadas fue capada por Google hace unas versiones. En principio solo lo puedes hacer siendo root, creo, tampoco es que esté muy puesto. Hay rumores de que en las próximas versiones de Android se va a recuperar.
Edito, dicen en otro hilo, que en la versión china si que se puede grabar llamadas. Incluso de forma nativa.