Have been using Office/OneNote 2013 for several months with no problems.
The last week, I open OneNote and it pops up a message "We're sorry. Onenote is cleaning up from the last time it was open. Please wait." A waiting bar displays and when it finishes, a new popup appears "It looks like OneNote is having trouble starting right now. If you keep seeing this message, restart your computer and start OneNote again. We're very sorry." Re-opening OneNote multiple times has the same result. Restarting the computer, and OneNote opens properly. However, soon (next day?) the problem happens again.
I see your thread is a few months old, but since it led me to my solution, I decided to reply to it in case someone else gets here with the same problem.
I worked in OneNote all day yesterday doing a variety of things and to my horror OneNote crashed on start-up this morning. My solution was actually very simple, but a bit time consuming.
I started OneNote and let it do its start-up "repairs." Next I went into the Recycle Bin of the notebook that I worked on yesterday and deleted everything in there. I had been experimenting with printouts and had a number of them in there. After that I went to File, Options, Save and Backup. From here I picked the option to optimize files. After running optimize two times, I ran a backup of all notebooks.
I closed OneNote, closed the OneNote Tool in Systray and then opened OneNote several times until I felt like the error was gone for good.
After closing OneNote, I went back to my Windows 8 Start Screen and typed %TEMP% and pressed Enter. If you are using Windows XP or Windows 7, you need to click Start, then Run, then type %TEMP% and press Enter. This opens up your Temp Directory and it is safe to delete everything in it, including the OneNoteRuntimeCache_Files Folder. As I said at the beginning, it is a bit time consuming, but OneNote is working well again.