Проверьте внимательно, что вы всё отправляете верно. Только что закончил задачу, похожую на вашу. Всё работает так, как написано в документации.
Сначала получаем access_token:
https://api.vk.com/oauth/access_token?v=5.21&client_id=<app_id>&client_secret=<app_secret>&grant_type=client_credentials
Получаем в ответ:
{access_token: <access_token>, expires_in: 0}
Затем выполняем запрос secure.checkToken:
https://api.vk.com/method/secure.checkToken?v=5.21&token=<user_token>&ip=<user_ip>&client_secret=<app_secret>&access_token=<access_token>
Получаем в ответ:
{response: {success: 1, user_id: <user_id>, date: 1400088413, expire: 1402680413}}
Дополнение: Я user_token получаю из flash_vars (access_token) из игрушки на флэше, а вы через мобильное приложение, возможно поэтому поведение отличается.