Godaddy seem to have a problem with UK domains. They show all of mine as Available, when in fact they are not,they are all in my 123-reg account. Your better of checking availability directly with Nominet.uk before attempting to register.
For some reason Godaddy show just about everything as available in UK. but obviously that fails at the registration stage. It's likely that everything your trying to register is already taken hence the 'failure notice'