Just had this exact problem. The tutorial fails to mention these two steps.
If you haven't yet, do the following:
- Add an image named ic_action_search.png to the 4 different res/drawable folders
Create a string named action_search in strings.xml
<string name="action_search">Search</string>
The main_activity_actions.xml fails to find those two things and doesn't add action_search to the R.java file, but doesn't give a useful error to point you in that direction.
Good luck!
EDIT: Also make sure you're using the app:showAsAction. As explained here.