It appears to be a Facebook caching issue - the UI is simply not refreshing and providing the new app options. However you can still submit the request with the required app id manually. I used firebug to inject my new app id and name into the <select>
element, and then submit the form as normal.
e.g:
1) Find the relevant input <select>
element:
2) Run this code in the Firebug (or equivalent) console, with the relevant [PLACEHOLDERS] replaced with your app id:
var fbidOptions = $$('select[name="fbid"]')[0];
var newOption = document.createElement('option');
newOption.setAttribute('value','fb:app_id,[PUT APP ID HERE]');
newOption.innerHTML = '[IT DOESNT REALLY MATTER, BUT PUT APP NAME HERE]';
fbidOptions.appendChild(newOption);
3) Select the newly injected option, and submit. The facebook servers will accept the app id as valid, leading me to believe its purely a UI caching issue.