I would suggest coming up with a new password entirely. Why? because if you are like a lot of people you reuse a few passwords in many places, maybe even just one password. So the next thing you'll want to do is go to every other important website,bank,computer you use with the same password as LinkedIn and change them too.
Having trouble coming up with a new password, here's some good advice from XKCD:
If you want to know if your password was taken you can also try leakedin.org to check your password, you may want to compute your password hash offline though rather trusting their site. If you have python installed (if you have a mac or linux machine this should be true by default) you can run the following on the command line to get your password encrypted and enter the resulting string into the LeakedIn website. Replace "password" with your password:
python -c 'import hashlib; print hashlib.sha1("password").hexdigest()'
(Thanks to Nathan Taylor for that snippet of code)