Here's one more answer that I found, after none of the previous 30 answers helped.
I found my issue in the strings.xml file, although it is very very odd.
I stripped down my app to bare minimum and this was the only thing that came to light. I can even replicate it on a brand new empty app.
In the strings.xml file, this compiles (and generates the R.java file):
<?xml version="1.0" encoding="utf-8"?>
<resources>
<string name="app_name">Test_My_App</string>
<string name="action_settings">Settings</string>
<string name="hello_world">Hello world!</string>
</resources>
However, this is not:
<?xml version="1.0" encoding="utf-8"?>
<resources>
<string name="hello_world">Hello world</string>
<string name="app_name">My_App</string>
<string name="action_refresh">Refresh</string>
</resources>
The "funny" thins is that I removed the action_settings several days ago. I've cleaned my code since then and never had any issues. I added additional strings to the strings.xml file today and after cleaning the code the wheels came off.
Also, if I re-arrange the order of the same 3 string lines, and clean my code, the R.java file does not get re-generated.
There's my solution to my particular issue.
I hope it helps somebody...