I experienced similar issues on Ubuntu 12.04 LTS and my case was fixed as below procedures.
sudo apt-get install apparmor-utils
The aa-complain command which referred by user2704275 is included in this package.
If your environment is RedHat/CentOS distro, you can same command by yum.
sudo aa-complain /usr/sbin/tcpdump
This will change AppArmor mode of tcpdump from "enforce" to "complain".
You can check AppArmor status in /sys/kernel/security/apparmor/profiles.
Then I can success to get tcpdump with sudo.
After getting tcpdump, for security reason, you might revert apparmor status to previous mode as below command.
sudo aa-enforce /usr/sbin/tcpdump
Regards.