I had a similar problem where the R.java file was not being regenerated after I'd added some icons and layout files. I tried cleaning and rebuilding and things got worse since then the original R.java file was gone and still wasn't regenerated. Eventually it dawned on me that there must be compiler errors for the compiler that generates R.java and we aren't being shown those in the console. Fortunately, I had noticed earlier that a) it's an error if one .xml file refers to another which is non-existent and b) it's an error to have upper case letters in your file names (why is that forbidden, I LOVE camel case).
Anyways, after renaming my icons and .xml files to all lowercase and then fixing all the references inside the .xml files, voila, R.java was regenerated. Just in time to feel good when I stopped for lunch :-)