Rachel,
This is pretty much exactly what happened to me and I've been dealing with it for about 6 months now. FIRST, I want to refer you to a Q&A I posted regarding this: http://www.seomoz.org/q/removing-unnatural-link-penalties
Next I'd like to say this - Find the service which was used to purchase these spammy links and contact them. For my company it was a site called "Submit Edge" and I was luckily able to login and download lists of articles published for us with usernames and passwords. Using these excel sheets I removed a good 300 links. That still wasn't enough and I wasn't able to remove the social media and directory links for the most part, but I knew where they were.
Use this list and attempt to contact webmasters and keep track of emails. Simply using the disavow tool will not be enough if you find you have been penalized manually. Google will want to see that you've worked hard to undo all of this.
It sounds like you haven't received a manual penalty message yet (make sure you check your GWMT daily to be sure) but there's still a chance it could come. I discovered and began trying to remove the spam links for my company's sites in late December and wasn't notified of penalty until mid-March. Luckily I had been tracking most of my efforts and am still putting together a re-inclusion request. (strangely, we have yet to see results of penalties so i'm admittedly dragging my feet a bit.)
There's also talk of a new Penguin update coming which could hurt your site when done. So the earlier you start and better you track your efforts the farther ahead you will get, I'd say.
Takeshi's advice is good. Just make sure you can show Google that you've tried really hard to identify this and fix it. That will prove to them that you know what your company did wrong and that it won't happen any more.
Good luck, keep us posted! These types of things are very interesting to me as it's what I'm dealing with daily.