Sorry for posting this as an answer, but I can't post replies yet. :(
I have the exact same problem, only some lists appear under the "Recent" node. I too declare the list to appear on the quick launch the same way, but when I check the list settings the "Display this list on the Quick Launch?" setting is set to no.
I think this behavior is new to SP2013, since I can't remember ever having this problem before.
If someone has a quick fix I'm all ears. Otherwize I guess there are some not-so-good solutions, such as adding a list event receiver for the ListAdded event and setting the property through code. Quite a hassle for something that should just work though.
Actually I think I have an answer now.
Speaking with a colleague of mine, he had the same problem a short while ago. He found that adding the list instance in the onet.xml instead of using a list instance did the trick. Because when adding list instances in the onet, SharePoint uses a different kind of element which has the "QuickLaunchHeading" attribute. This attribute is not present in the ListInstance element. So in the configuration element, you could add lists like so:
There are some drawbacks to this though. You cannot be sure of the order in which stuff is provisioned, so you cannot activate a feature which is depending on the list. Just to clarify I haven't tried this yet, so my answer may not be 100% complete, but I will try it soon though. :)