Moving plans may potentially cause inconsistencies in the build table where incorrect branch keys are inserted into the build table.

If you moved plans and restarted Bamboo, that could cause the same issue. Meaning, contrary to the first impression you might have after reading the logs, this won't happen necessarily during an upgrade task. The following can be seen in the logs:

2015-06-04 10:05:23,636 INFO [localhost-startStop-1] [AbstractUpgradeManager] Completed task 4410 with errors.
2015-06-04 10:05:23,636 FATAL [localhost-startStop-1] [DefaultBootstrapManager] Pre-bootstrap validation tests failed: [Task for build 4410 failed:, com.atlassian.bamboo.upgrade.tasks.validation.BranchKeyStartsWithMastersChainKey: There 
are invalid branch keys in the BUILD table: [BIS-SNATRUNK3]]

Workaround:
If you're hitting this and your instance is down, the following procedure should be applied so you can get your instance up and running:

1. Stop your Bamboo instance.

2. With Bamboo stopped navigate to

<Bamboo Install Directory>/atlassian-bamboo/WEB-INF/classes

and open the upgrades.xml file.

3. Find the following line:

<upgrade build="4410" build-min="4410" build-max="9999"             class="com.atlassian.bamboo.upgrade.tasks.validation.BranchKeyStartsWithMastersChainKey"/>

and update it by commenting out the entry to:

<!-- <upgrade build="4410" build-min="4410" build-max="9999" class="com.atlassian.bamboo.upgrade.tasks.validation.BranchKeyStartsWithMastersChainKey"/> -->

4. Save the file Restart Bamboo.

5. Get an export of your instance.

6. Raise an issue with https://support.atlassian.com and attach your export so we can double check the database consistency.

7. Once that's done, you should set your upgrades.xml back to uncomment the tag you commented out on the step #4 of this procedure.