I think that comic-Searle's position is basically correct, that as a social fact princehood is a consensus hallucination, but he misses the fact that there are many ways for the genie to get an entire nation to believe that Aladdin is a prince; a clever genie is not limited to the direct manipulation of minds in order to fulfill this wish.
Let us assume that the genie is bound not to violate causality or free will, and has a strong preference against the use of force or violence. Further, let us infer from his discomfort in the tenth panel of the comic that the magical conjuration of an entire nation out of nothing is also in some way off-limits. And finally, let us impose a time limit of a few days or at most a week or two for the jump cut between the declaration of the wish and Prince Ali's debut. Even with all these constraints, a plethora of options remains available. Consider:
1) The genie uses his magical powers to identify a distant monarchy that is currently undergoing a crisis of succession. He travels to this faraway principality of Babwa and presents them with conjured evidence that Aladdin is the proper heir. The Babwans agree and acclaim Aladdin as prince, et voila! This is essentially fraud, but that doesn't seem out of character for the genie. The major difficulty I see is the possibility that the presentation of a previously unknown heir, despite the supporting evidence, would not suffice to resolve the crisis, and that a great deal of effort would then be expended in maintaining the throne. That, and finding such a situation ready and waiting when the wish is made.
2) If no such situation can be found, the genie could instead look for an elective monarchy in the throes of a crisis of any kind. The genie could offer to resolve the crisis using his magic if the electors will declare Aladdin the new heir. (This approach also satisfies the Kripkean requirement for legitimacy, by the by.) Of course, while the odds of finding an specific type monarchy with a generic crisis conveniently underway may be marginally better than the odds of finding a generic monarchy with a specific type of crisis, in neither case are the odds particularly good.
3) The genie could instead use his powers to find an elective monarchy, manufacture a crisis, and resolve it. This seems much more practical, but it may push the limits of the genie's ethics; while he seems happy to trick people, trafficking in wholesale blackmail and extortion may run too close to use of force. In addition, the time required to both set up and resolve such a scam may be difficult given the time limit.
4) The genie could establish the principality of Babwa, not by magic, but by social manipulation. Find a small group of people in some out of the way place and offer them a fabulous reward if they declare themselves a sovereign nation with Aladdin as their prince.
5) The genie could create Babwa through transmutation rather than ex nihilo. He could select a group of living creatures and, via temporal acceleration and controlled magical augmentation, rapidly evolve them to sapience and guide the development of a society that would regard Aladdin as their monarch. Perhaps Babwa occupies a single mote of dust, a la Seuss's Whoville, an the Babwans are hyper-evolved mites from Aladdin's own follicles.
Et cetera. Those are just the first few ideas that occurred to me. I'm sure we could think of more.
Note that the context of Aladdin's wish very strongly implies that he doesn't just wish to become a prince, he wishes to become a prince in order to woo Princess Jasmine. And since the genie is operating in a mode of benevolent generosity rather than malicious compliance, he desires to fulfill the spirit of the wish as well as the letter. Which means that it will not suffice for him to merely make Aladdin a prince in the abstract, but in the eyes of the people of Agrabah, particularly the Princess and Sultan, as well. (Which is where Searle's definition of princehood comes into play.)
So regardless of how he makes Aladdin a prince, he also needs to make a convincing presentation of Prince Ali's bonafides to all of Agrabah. Hence the fancy duds (especially the hat), the big musical number, and the princely retinue of camels, peacocks, monkeys, slaves, servants, flunkies, elephants, llamas, bears, lions, brass band, fakirs, cooks, bakers, birds, and more. The great spectacle is necessary for Aladdin to be a prince in the eyes of Agrabah.
Now, consider. The genie is likely the only one who knows which the details of which option he chose and exactly how he caused the state of princehood to be conferred upon Aladdin. The actual state of Babwa's line of succession is well outside Agrabah's informational horizon. Agrabah must -- and is shown to be content to -- update its beliefs about Ali's princeness based solely on the available information: the great spectacle is not only necessary, it is sufficient.
That being the case, does Aladdin's actual status in Babwa matter at all? Does the genie need to pick any of the options? If reports were received of some disaster that severed all communications between the two locales for a span greater than one man's life, would Prince Ali's status be revoked? What about a disaster that also prevented any reports? Is Prince Ali's princeness somehow retroactively contingent on the unknown possibility of hypothetical communications?
The answer to all these questions is no! Because whether Aladdin counts as a prince in Agrabah depends on whether the society of Agrabah agrees that Ali is a prince of Babwa.
Which they do (at least until Jafar's interference (temporarily) negates the wish), because the genie changed the society of Agrabah (not Babwa) to make them believe that Aladdin is a prince. And he did it not by interfering with their minds, but by presenting Ali as a prince and providing a surfeit of corroborative evidence in the form of princely trappings -- which is to say, via the hat and the song (et cetera), exactly as the genie attempts to explain in panels 12 and 13.
Aladdin did, in fact, have his wish granted the whole time. Aristotle is a dope, the philosophers need to listen better, and Aladdin needs to quit trying to rules-lawyer his way into extra wishes.