Here's a script for removing nova instances from your DB.

gistfile1.txt

#!/bin/bash
#
#    This program is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation, either version 3 of the License, or
#    (at your option) any later version.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    <http://www.gnu.org/licenses/>.
#

#VMNAME=$1
UUID=$1

if [ -z "$1" ]; then echo "VM ID not given"; exit 1; fi
Q=`cat <<EOF
SELECT id FROM nova.instances WHERE instances.uuid = '$UUID';
SELECT uuid FROM nova.instances WHERE instances.uuid = '$UUID';
SELECT display_name FROM nova.instances WHERE instances.uuid = '$UUID';
EOF`
RQ=`mysql --batch --skip-column-names -e "$Q"`

ID=`echo $RQ | cut -d' ' -f1`
UUID=`echo $RQ | cut -d' ' -f2`
VMNAME=`echo $RQ | cut -d' ' -f3`

if [ -z "$ID" ]; then echo "ID for $VNAME not found"; exit 1; fi
if [ -z "$UUID" ]; then echo "UUID for $VNAME not found"; exit 1; fi

echo "VMNAME: $VMNAME"
echo "ID: $ID"
echo "UUID: $UUID"

echo "Delete $VMNAME? (y/n)"
read -e YN
if [ "$YN" != 'y' ]; then echo "Exiting...";exit 1;fi


for Q in \
"DELETE from nova.instance_actions_events where action_id in ( select id from nova.instance_actions where instance_uuid = '$UUID' );" \
"DELETE from nova.instance_actions where instance_uuid = '$UUID';" \
"DELETE FROM nova.instance_faults WHERE instance_faults.instance_uuid = '$UUID';" \
"DELETE FROM nova.instance_id_mappings WHERE instance_id_mappings.uuid = '$UUID';" \
"DELETE FROM nova.instance_info_caches WHERE instance_info_caches.instance_uuid = '$UUID';" \
"DELETE FROM nova.instance_system_metadata WHERE instance_system_metadata.instance_uuid = '$UUID';" \
"DELETE FROM nova.security_group_instance_association WHERE security_group_instance_association.instance_uuid = '$UUID';" \
"DELETE FROM nova.migrations where instance_uuid = '$UUID';" \
"DELETE FROM nova.instance_extra where instance_uuid = '$UUID';" \
"DELETE FROM nova.instances WHERE instances.uuid = '$UUID';"
do
  echo $Q
  RQ=`mysql --batch --skip-column-names -e "$Q"`
  echo $RQ
done