This particular message happens when a nonce check fails.
I'd say the likely cause is a conflict with the referer (as part of nonce security, WP checks to see if the referer was an admin page on the same domain & path).
You can rule this out by defining a custom function in wp-config.php
:
function check_admin_referer($action = -1, $query_arg = '_wpnonce') {
if ( -1 == $action )
_doing_it_wrong( __FUNCTION__, __( 'You should specify a nonce action to be verified by using the first parameter.' ), '3.2' );
$adminurl = strtolower(admin_url());
$referer = strtolower(wp_get_referer());
$result = isset($_REQUEST[$query_arg]) ? wp_verify_nonce($_REQUEST[$query_arg], $action) : false;
if ( !$result && !(-1 == $action /* skip this: && strpos($referer, $adminurl) === 0 */) ) {
wp_nonce_ays($action);
die();
}
do_action('check_admin_referer', $action, $result);
return $result;
}
This implements the standard nonce check, but skips the referer part. If it cures the error message, we've isolated the problem and can work towards a permanent fix.
Further reading on the two primary types of errors (this, and insufficient permissions).