Been there, experienced that... took me a long time to learn how to deal with it properly.
If you have not create one yet, do it now! I am talking about IT policies and a ticketing system.
Create a priority system, plenty of choices. My personal choice is a 5 priorities system. Keep it simple. Users won't read more than one paragraph anyway.
1 - very low priority, I get to it when there is nothing else to do.
2 - low priority, but need to be taken care of sometime this quarter
3 - normal priority, need to be taken care of within 5 business days
4 - high priority, to be resolve within a business day
5 - burning, must be dealt with now.
Then setup a helpdesk ticketing system. Again lots of choices. Personally I'd use opensource, currently using OTRS (also used Cerberus, which I like). Let that be your records if your users want to know what you've been doing. Set it to have all incoming request default go 3 (or 4).
At first your users will scream, make lots of noise, etc. Just stick to your policies. In the beginning there will be jerks who demanded they are taken care of first. Gently steer them to the helpdesk system, create their tickets for them. I've had people call me on the phone, IM me, badger me in the hall, while I am eating lunch, etc. Just tell them to open a ticket, or that you will open one for them when you are finish with what you are doing. Put up a web page that show your queue, what the priorities of those tickets are etc... Pretty soon it will be obvious who waste a lot of time, who always made their the highest, etc.
One of a few things will happen...
* all of your tickets will be 5 :-) tell them (and show them/your boss) and ask him/her to prioritize for you.
* people learn to do things for themselves and you'll have time to handle more urgent company matters
* you found another job