At least in Mac OS X 10.8+ with recent versions of Wireshark (1.10.8 tested), it’s simply a matter of running the following command:
sudo sh /Library/Application\ Support/Wireshark/ChmodBPF/ChmodBPF
Not sure why WireShark can’t just prompt and do it automatically, but this seems to fix the problem.