I know exactly why your hosting provider needs your root password - that's because it's absolutely impossible to tell whats wrong with your server without a valid login, preferably root. If your machines aren't showing orange hardware failure lights, and you have no proof or data on a networking outage, then it's 90% sure to be an issue with the software on your machine. Since it's the most likely problem, it's unreasonable to expect your hosting provider to immediately spend a lot of time investigating the last 10%.
You have two options (three actually):
1) Provide a root login
2) fix it yourself (this may require going to the datacenter in person)
3) see if they can work with an account with limited priviledges (it must be able to read logs and see all processes at the least). You also might want to try posting on serverfault - I can't comment on the technical end as you've supplied no detail
Actually the support staff would probably be happiest if you fixed it yourself. In addition, have you considered that they may have brought down your machine or machines, to run memtest86+ or the like? Are you *sure* they rooted it?
My only advice is to see if they'll accept a limited account (that can go through logs and see all the running processes).