There's no obvious way to do this efficiently. For small n, you might as well just us the formula to calculate the inverse PDF. For larger n, you're probably best off using one of the approximations to other distributions that are easier to calculate.
If you are willing to pay, then take a look at NMath by Centerspace.
Otherwise, the C code used by the Stats program R is here, and should be straightforward to port to C#.
EDIT: There are details (inc. code) on creating a method for this on p178 of Practical Numerical Methods with C# by Jack Xu.
ANOTHER EDIT: A free C# library that does what you want.
Another option would be to sample from Normal or Poisson as you do and then add a Metropolis-Hastings step to accept or reject your sample. If you accept you are done, if you reject, you have to completely resample again. My guess is that because the approximation is so close, you will almost always get an accept step, once in a while you might reject.
Also Luc Devroye's book has some great algorithms for Binomial sampling.
PS If you end up with a good algorithm; would you mind sharing it at Math.Net Numerics?