We are storing hashed passwords in a database table.
We prepend each password with a random salt value and hash using MD5CryptoServiceProvider.
Is this safe? I have heard MD5 was "broken".
If not, can you recommend an alternate hash method to use (specific .NET framework class)?
With a salt MD5 is much more secure than without, but you're better off using one of the SHA hashes such as SHA256Managed.
Storing hashed password is better since it hides the password from prying eyes of DBA's.
Also, yes, MD5 was broken, but is still used to this day. If you are concerned about MD5, rather use SHA-1 (MSDN link here). It's a hashing algorithm just like MD5 but stronger. You can have SHA-1 hashing of up to 512 bits.
Here's an example done on VB.NET (http://www.obviex.com/samples/hash.aspx).
Here's the US Department of Homeland Security stating why people should move away from MD5 (http://www.kb.cert.org/vuls/id/836068). Summary, it's "cryptograpically broken"
The security of a hash function mainly comes from the length of its output (message digest): a longer digest gives greater collision resistance. The birthday paradox tells us that on average you'd expect to find a collision from a work function of the square root of the digest size: in other words, given a 128-bit digest, an attacker would expect to hit paydirt after 2^64 trials.
MD5 has been frowned upon by the cryptographic community for some years now because it only has a 128-bit digest, and there are also some interesting cryptanalytic results which might effectively reduce its strength. SHA1 (160 bit digest) had been the preferred alternative, but even then it is starting to look like it was not long enough for a well-motivated adversary and there are also some interesting results in the research community. The SHA-2 family (output sizes from 224 to 512 bits) are the current preferred hash functions in widespread use. There is an active research competition organised by NIST to find a successor for SHA-2, but we won't have a new standard until 2012 or so.
Now, in the specific case of storing passwords, I note you are using a salt. This is the strongly recommended practice; without a salt you would be vulnerable to a rainbow table attack. I believe that this leaves you with only the brute force attack to consider; this is where keylength.com comes in. It brings together recommendations for key and digest sizes from across the cryptographic community and gives expected security timescales for various algorithms, considering current computing power and taking Moore's Law into account. Consider what sort of assets you are protecting and how long you need to a password to remain secure for (do you have an enforced password change policy, for example?) and that should pretty much answer the question of the digest size you need.
Of course, the best password storage in the world won't help you if your users use easy-to-guess passwords. Do you provide your users with tips for strong passwords? Have you considered a password strength meter or similar?
No, you shouldn't be using MD5. But you shouldn't be using a single round of any general purpose hash function, no matter how cryptographically secure it is, either! Not MD5, not SHA-1, not SHA-2, not SHA-3.
Why? Because general purpose hash functions are designed to be fast. And fast is exactly what you don't want in a password hash. Fast means that when the bad guys get your database, they can run a plain old dictionary attack against it in a reasonable amount of time.
What you need is slow. The simplest way to be slow is to iterate the fast hash function thousands of times - that's what the MD5 and SHA-1 based password scheme used to store passwords on UNIX-like systems do (it's not just one round of MD5 or SHA-1). Another way is to use a cryptographic primitive that is designed to be slow - that's what the "bcrypt" password scheme does.
This Matasano article, What You Need To Know About Secure Password Schemes, has some good reading on exactly this subject.