I am starting up a new company with 3 others which is going to be a software/web company. I have already started on writing the software in C# 4.0, as I have a VS 2010 license, but my other partners don't have Visual Studio licenses, so we want to try one of Microsoft's startup offers. My question is: which should we use, Bizspark or WebSiteSpark, and why?
Depends on what your business plan is; true software development startup or more of a web design bureau? Have a look at this older question first.
BizSpark has more enterprise software included in it (SQL Server Enterprise, SCOMS, Sharepoint, see here. Compare that with WebSiteSpark here.
On the flip side, BizSpark may be harder to get accepted into. That may or may not be just a rumor, but I have heard several people state they were not accepted into BizSpark, and so far I haven't heard anyone say the same about WebSiteSpark.
If you have a startup then you need to apply for BizSpark. If you are a consultant, then WebSiteSpark is the program for you. The rumors you mentioned are just that, rumors. I have been accepted to BizSpark and know many other startups who have been accepted as well.
Tip: Make sure you have a MS employee refer you to the program, as a sponsor to increase the chances of getting accepted.