Site below says 1880.

but not for "beef" as a "complaint" - only for "beef" as "yell". The former meaning is given as dating back only as far as 1950.

Been racking my brains, trying to think up where/how it might have arisen....Because Wendy's (hamburger chain, for those who haven't heard of it) had that famous "Where's the beef?" ad far more recently than the '50s - otherwise that might have been the answer.