One could probably obtain the package names of all the apps out there, so, as long as package names can be used to access components in Android, this is information that could be extracted by trial and error anyway.
On the other hand, everything you can do with this knowledge is controlled by sandboxing and permissions, so having this knowledge doesn't give you anything beyond what you could have with a good guess.
Lastly, one would have to reinvent package naming around names that cannot be guessed. To sum it up, package names weren't designed to be private, and retrofitting privacy to package names is hard.
I disagree when you say " everything you can do with this knowledge is controlled by sandboxing and permissions, so having this knowledge doesn't give you anything beyond what you could have with a good guess." because this information can be used to later push application-specific ads or even try to present the user with data in order to make him click on an ad or link and get exposed.
This is no serious Remote Code Execution hack but is definitely a worrisome information leak.
The developers' domain names are public, so there is no way to prevent guessing parts of package names in Android and probably no way to prevent guessing complete package names.
Let's take a use case: I want to secretly check if you have banking apps installed. I can install them and discover their package names. Then I can make a malicious app that checks if some component of those apps exists, by checking for an intent filter match, for example. Then I present you with a targeted phishing attack that looks like those apps' screens. You didn't need to enumerate all installed packages to do that.
There are legitimate uses for enumerating all the packages. I've used it for a plug-in architecture for an app that enables 3rd party plug-ins.
And I also agree with you that there are legitimate uses for that, as you have for sending/receiving sms, but my point is: Users should be warned that this app is attempting to do that so they can judge where to install it or no, as you have for all other sensitive information.
I think all your points on both comments are good and valid and I'll update the post with that. Thanks for your opinions.