I'm using WordPress HTTPS to force SSL encryption on my dashboard.
Because of this, the polls no longer worked, voting or viewing votes resulting in an "Unable to verify referrer" message.
After browsing around for a solution, I found out that modifying the plugin (specifically the wp-polls.php file) and changing
'ajax_url' => admin_url('admin-ajax.php'),
in the polls-script() function to
'ajax_url' => admin_url('admin-ajax.php', (is_ssl() ? 'https' : 'http')),
solves this issue.