The above post is correct regarding the name, or existance, of the store being required.
When you open Exchange System manager and drill down to the server, you will see at least one Storage Group, or more if you added any. If you took the defaults, and only have one Storage Group, your Public Folder Store must be in the first storage group. Expand the Storage group, you should see at least one mailbox store and one public folder store (the minimums).
Compare what is shown on your Exchange Server to what you see in the restore selections for your exchange database. If in BE you see Storage Group 1 has two mailbox stores and one public folder store, you must have the same names in Exchange System Manager. For Instance, if you Public Folder is named "Internet Newsgroups" it must have the same name in Exchange's directory structure.
In short, whatever you see listed in the BE restore selections under Exchange, verify the names match exactly to what you see in Exchange System Manager. Also, if the names match already, make sure the public folder store is mounted (no red x next to it - right click and mount it if you see the red x)