Possible short answer: did the account you applied for have an overdraft facility? If so, you'd need to meet the more stringent criteria for being lent to (rather than the easier criteria for being borrowed from, as a current account holder), which with a limited financial history would be hard. It may be worth getting the GBP 2 statutory credit report from each of the credit reference agencies and checking that everything you expect is there, and nothing you don't is.
In general, it's not as simple as 'reasons X, Y and Z caused this'. The financial institution will look at you, first check that you don't trip any red flags for the product you're applying for, and then (possibly using credit reference agencies) calculate a score for you. If the score meets the threshold for the product, they'll accept you for it; if not, they won't. Typically they won't go into more detail than this, in their rejection letter.
my first permanent address with my first full-time job. In recent years I have lived at many different properties. ... I have a typical student current account
All of these facts will make it harder for you to have a sufficiently high score. FIs want to see evidence of being settled (many recent addresses is 'bad') and having a record of meeting financial obligations (a student account is not particularly good such evidence), and of being likely to be able to meet future finanical obligations (just started first job says not a lot really).
This is interesting, though:
and have never missed any payments on anything.
If you've been incurring and paying regular bills for some time, as this suggests, that would be a positive. Are we talking utility bills, mobile phone contract, and such? With your multiple recent addresses it may be that not all this data is attached to you - the credit reports would show this.
Finally I note:
Despite this I feel my credit should be reasonable.
Things in this sphere don't necessarily work in the obvious way. I know of someone who was earning close to six figures who was turned down for an unremarkable credit card from a UK bank, simply because they had never borrowed before and so had no way of showing themselves to be trustworthy. They had to get one from, essentially, a subprime CC lender and hold it for a year to build a borrowing history for themselves.
No FI wants to be the first to lend to someone unknown, unless it's with a hefty APR...