[edit] This is a comment on the excellent answer by Stephen Harris.
It doesn't return any terms if used with multiple post types like this $flags = wpse57444_get_terms('flags', array('post_types' => array('country','city')));. This is because $wpdb->prepare sanitizes the $post_types_str string to p.post_type IN('country,city') while it should be p.post_type IN('country','city'). See this ticket: 11102. Use the solution from this topic to get around this: http://stackoverflow.com/a/10634225