Several context-aware mobile recommender systems have been recently proposed to suggest points of interest (POIs). Ideally, a user of these systems should not be allowed to know the preferred POIs of another user, since they reveal sensitive information like political opinions, religious beliefs, or sexual orientations. Unfortunately, existing POI recommender systems do not provide any formal guarantee of privacy. In this paper, we report an initial investigation of this challenging research issue. We propose the use of differential privacy methods to extract statistics about users' preferences for POIs. Actual recommendations are generated by querying those statistics, in order to formally enforce privacy. We also present a high-level architecture to apply our methods.