I have found out why this is happening....
I have included 3 menus on my page. I have one that is going across the top, one going across the bottom, and then the multi-level menu.
The problem is I am mixing the types of menus that I want to appear.
In my case, the first menu to load was the top one that doesn't have multi-levels. This item was not loading the submenu items. Well, when this loads, it puts the items in the cache. The same cache that the multi-level pulls from.
When I modified this to pull from different cache locations, there were no more problems.
Thanks,
Keith