So, our guild is almost about to down Nefarion, and then we'll probably spend a little while gearing up through BWL. My question is, where would you guys reccomend we go next? Start AQ40? Or try the first few Naxx bosses? I myself think we could already take one or two bosses in Naxx, but I've also heard that AQ40 isn't so hard either.

Try both. Go to AQ for a week and see how far you get. Go to Naxx for a week and start with Razuvious and Anub'Rekhan. And then decide. There's no "right" answer, and there have been roughly a million threads on this subject.