Using setcookie in a plugin

I am writing a plugin that needs to use a cookie to track if a user has completed a survey. The plugin runs from a shortcode placed on a page. My problem is that as the shortcode is executed after the headers are sent I can’t set the cookie – well at least I think that is why it is going wrong. This is the error message I get:

Warning: Cannot modify header information – headers already sent by (output started at /home/mynerjac/public_html/frbf/wp-content/plugins/all-in-one-seo-pack/aioseop.class.php:221)…

Any ideas how I can get round this?

This is the code I am using to set the cookie (and nothing has been echoed before this code):

$expire=time()+60*60*24*30;  //Expires in one month
	$url = parse_url(get_option('home'));
	setcookie( $cookie_name, "done", $expire, $url['path'] . '/');