I found this forum post on the SEF Service Map site which is the same problem I'm having. They don't provide a real solution but suggest that there is a problem with JoomSEF. Please take a quick review and let us know if what they are talking about make sense.
file: /components/com_sef/joomsef.php
function _sefGetLocation
Lines with wrong column definition:
$col = $val = '';
if( isset($Itemid) && ($Itemid != '') ) {
$col = ', `Itemid`';
$val = ", '$Itemid'";
}
$query = 'INSERT INTO `#__redirection` (`oldurl`, `newurl`'.$col.') '.
"VALUES ('".$temploc."', '".mysql_escape_string(html_entity_decode(urldecode($url)))."'$val)";
$db->setQuery($query);
// If error occured.
if (!$db->query()) var_dump($query);