Hmmmm...this doesn't make sense. Since I rarely ever pay attention to nor really care for administrative stuff like this, I'm open to the possibility that things have changed, but here is what the Stern school says about it as of right now (I'm assuming this is accurate, its for the class of '08):
Q: Can I complete a major within the College of Arts & Sciences?
A: Stern students may only major within Stern. However, Stern students may minor (except for economics) within the College of Arts & Sciences. (CAS)
Check out:
http://w4.stern.nyu.edu/emplibrary/FAQ_for_Freshmen.pdf
Then of course there is the example of matth's friend who seems to contradict this established rule...so I think the best thing for anyone interested in this to do, is ask the Stern school directly (the school itself, not the admissions office). FYI, on non-admissions related matters, I would not take everything the admissions bulletin board says as 100% correct since these are areas that are out of the admissions office's realm, and thus the bulletin board may not be infallible.