jslate, I hope you are getting some reassurance from the fact that almost everyone posting has a slightly different approach :-)
I think the first couple of steps you listed there were *technically* unnecessary - while the approach you've taken is the automatic / systematic one I daresay everyone reading it would have taken too, the interviewer told you that the printer isn't available in Windows - hence it's not a physical problem.
As an aside, rolling back the SP on all the machines makes the assumption that the service pack is less important than having the printer available - if there was a critical vulnerability you might want them SP'd no matter what - so there's an element of prioritisation in there.
The Office service pack is too much of a coincidence to ignore, however REALLY what are the chances of an Office SP removing a printer from Windows?
This seems so unlikely to me that I'd be tempted to ask if any other changes had happened at the same time, and related to that is finding out who did the change, and HOW it was done. It may be that it wasn't the installation itself that caused the problem, but how it was implemented.
If it was simply that the SP was applied, then go into a bit more in-depth troubleshooting.
The only other thing I'd pick up on is the penultimate line - if you're troubleshooting, you don't need to make the change to all PC's, just one or two.
Checking online seems to be a controversial answer - given that a University helpdesk is likely to have several staff, I'd say it was valid to consult with a colleague rather than hitting the Internet straight away - particularly when starting in a new environment, as it's quite possible the experienced person will say "Oh, has it done *that* again?!".
When we're interviewing we are wanting to see that people are thorough, but also fast, and so I'd favour someone who asked for help over someone who beat their head against a brick wall (the brick wall phase is appropriate *after* you've got no useful help), assuming they'd first carried out a process of troubleshooting appropriate to their 'level'.
There is no right answer. The question is designed to look at how you aproach the troubleshooting process. If you just said "i dont know" then obviously it wouldn't look good for you, but remember this is an interview question so you will be answering with a little bit of nerves(probably). It's easy for us to give a few different views of how to answer, but in an interview I always try to say the things to look at are"Blah Blah...", but not necessarily in any order. In reality things would be tested before rolling them out and chances of something like this happening are slim. By giving an answer which gives a number of things that would be looked at and then showing that you are willing to take advice rather than try and solve it on your own is probably the only thing they are looking for as an answer.
Maybe (I think someone has already said) that you could have said ask someone else or refer it higher before researching on the internet.