The function that searchs for permissions uses the translated name -t()- instead of the original name that shows in the tables. A possible solution is using a new function that returns the untranslated name for everything but the user interface. This is how my setup looks now:

/**
 * Implementation of hook_node_name().
 */
function flexinode_node_name($node) {
        return t(untranslated_flexinode_node_name($node));
}

function untranslated_flexinode_node_name($node) {
  $type = is_string($node) ? $node : (is_array($node) ? $node['type'] : $node->type);
  $ctype = flexinode_load_content_type(substr($type, 10));
  return $ctype->name ? $ctype->name : 'flexible content';
}

/**
 * Implementation of hook_access().
 */
function flexinode_access($op, $node) {
  global $user;

  if ($op == 'create') {
    return user_access('create '. untranslated_flexinode_node_name($node) .' content');
  }

  if ($op == 'update') {
    foreach ($node as $fieldname => $field) {
      if (preg_match('!flexinode_[0-9]+_format!', $fieldname) && !filter_access($field)) {
        return FALSE;
      }
    }
  }

  if ($op == 'update' || $op == 'delete') {
    if (user_access('edit own '. untranslated_flexinode_node_name($node) .' content') && ($user->uid == $node->uid)) {
      return TRUE;
    }
  }
}