diff --git a/exercises/euca.sh b/exercises/euca.sh
index 982653e..76df254 100755
--- a/exercises/euca.sh
+++ b/exercises/euca.sh
@@ -165,8 +165,11 @@
 euca-terminate-instances $INSTANCE || \
     die "Failure terminating instance $INSTANCE"
 
-# Assure it has terminated within a reasonable time
-if ! timeout $TERMINATE_TIMEOUT sh -c "while euca-describe-instances $INSTANCE | grep -q $INSTANCE; do sleep 1; done"; then
+# Assure it has terminated within a reasonable time. The behaviour of this
+# case changed with bug/836978. Requesting the status of an invalid instance
+# will now return an error message including the instance id, so we need to
+# filter that out.
+if ! timeout $TERMINATE_TIMEOUT sh -c "while euca-describe-instances $INSTANCE |grep -v \"InstanceNotFound\" | grep -q $INSTANCE; do sleep 1; done"; then
     echo "server didn't terminate within $TERMINATE_TIMEOUT seconds"
     exit 1
 fi