GCM을 쓰려면 Google Play Services가 있어야 한다는 말입니다.
에뮬레이터에 play store가 없는 상태겠네요. 구글에서 gapps인가로 검색하시면 에뮬레이터의 안드로이드 버전에 맞는 google apps를 구할 수 있을 겁니다. 그걸 설치하시고 실행해보세요.
그리고 참조하신 사이트가 최근 사이트는 아닌 것 같습니다. play service 6.5 이상부터였나 meta 정보가 반드시 들어가야 했던 것 같습니다. 보다 자세한 건 구글 디벨로퍼 사이트의 Google Cloud Message부분을 참고하시면 될 겁니다.