I can't tell from your description if what you're trying to predict is a continuous-valued response or a binary (dichotomous) response. If it's a continuous-valued response, you have a regression problem, and you want to use some kind of a residual-based loss function such as MSE. If it's a binary-valued response, then precision and recall are exactly the right measures to use.

Ok, so your question is: what evaluation metrics should one use for Collaborative Filtering. This is a continuous-valued response (unless you've dichotomized it, which some people do recommend), and you want to use some kind of a residual-based loss function such as MSE. The Netflix Prize competition used Root MSE.

There's lots of materials on evaluation of CF. You might also watch Andrew Ng's lectures on CF, see under XVI. Recommender Systems.

Also, make sure that your MSE computation is working right: make a fake recommender that peeks at the validation set to produce correct responses at least 10%, 30%, 50%, 70% of the time and see if the MSE drops.