What version of Linux were you using? I was hoping these sorts of hard drive corruptions were a thing of the past.
I've
warned of this danger. It sounds to me like Linux may have messed up the file system on your C:. I only expect the problem to get worse and worse as time goes on. I had this happen, as did a friend of mine (no-thanks to Live Linux 0.2... fortunately it was on our E: drives that we had corruption, not our C: drives).
I'm sorry about this wretchedly bad news. You could fix it, as I did on my E:, but since this is your C: showing corruption, at this point fixing this is quite risky itself.
If you follow these directions and it doesn't work, you'll probably end up with a dead Xbox and chances are nobody will be able to help you. I take no responsibility for your decisions on how to handle this situation or the results of any of the steps taken below. But if you follow these directions and it does work, then the problem will be all fixed.
First, download a copy of your C:... get every file that you can, unless it looks like there is an infinite amount of files due to something repeating (pointing to itself or a parent) in the file system. You may need to do a lot of this manually... hopefully an automatic download of all the subdirectories will work fairly painlessly. Note that you should do this step as soon as possible (before the file system corruption gets worse).
Alternatively, you may want to "create" (I surely wouldn't recommend piracy by obtaining it elsehow, since I surely wouldn't recommend piracy on these forums) the files on the C: from another Xbox. Just make sure it has a dashboard at least as new as yours, if you have a Kernel of 5713. (If you have an older kernel, it doesn't matter.)
Then, and this is the really risky part, format your C:. I recommend doing that in Evolution-X RemoteX, just because I did that with my E: and there were no problems resulting, so I consider that software tested by myself. You may need to edit the evox.ini file to allow for this. Another option would be UnleashX, which seems to be high quality software: I just haven't tested it's formatting.
Then, as soon as the Xbox hard drive is done formatting, restore the dashboard. Do this either from your back up (and hope like heck that your backup didn't have corrupted files).
If you do this, and reboot, and things work on your Xbox, and you did this with no files except those on your hard drive, I would suggest connecting to the "Xbox Live!" service to download the latest dashboard, or run a game that will update your dashboard. (This only works if the game has a newer dashboard, or in the case of "Xbox Live!" which always has the newest dashboard, if you don't have the newest.) Then you can rest easy if the dashboard update goes well, knowing it is unlikely you have any corrupted dashboard files. (I suspect MS might treat a corrupted file as a hacked file, especially if using "Xbox Live!" to update.)
Again, please reply with info on what Linux you were using.