According to John Mariani's Encyclopedia of American Food and Drink (1979): "The word is from the Janaese negi (onion) plus maki (wound around). The dish, which has become popular in Japanese restaurants in the United States, was created at New York's Nippon Restaurant in 1963 by owner Nobuyoshi Kuaoka under the prompting of New York Times restaurant critic Craig Claiborne, who thought the restaurant should have more interesting beef dishes for the American customer. Kuaoka originally called the dish 'negimayaki.'"
That should solve it, but it doesn't. A New York Times text search of "Claiborne" and "Nippon" doesn't turn up anything relevant. I tried "negimaki" and "negimayuaki" and "negima-yaki," with the results below. The Los Angeles Times digitization is now through 1964, and I'm still waiting for a "California roll" in its pages. If I see an earlier "negimaki" or "negimayaki," I'll add it here.
11 November 1963, New York Times, pg. 37:
They are the Nippon at 145 East 52d Street, and the new Saito at 131 West 52d Street (...) Although sushi may seem a trifle "far out" for many American palates, such dishes as teriyaki (steak, pork or chicken marinated in soy sauce and grilled), shiwo-yaki (pork or chicken broiled with salt and served with a soy and lemon sauce), as well as the familiar tempura and sukiyaki, have an immediate and almost universal appeal.
(It's not mentioned here -- ed.)
5 December 1975, New York Times, pg. 55:
Among the appetizers (we give prices of full portions here - you get smaller poritons with dinners) we had an excellent negimaki - beef wrapped around scallions with teriyaki sauce ($2.75).
23 December 1977, Valley News (Van Nuys, CA), pg. 41, col. 2:
Inagiku Menu Highlights
9th Floor, Bonaventure Hotel
5th And Figueroa, Downtown Los Angeles
(...) negimayaki, $2..50 (...)
13 April 1979, New York TImes, pg. C18:
Negima-yaki, tender beef roll-ups wrapped around scallions and broiled in a soy marinade, were lovely and firm one night, but at another time were much too soft and drowned in sauce.
(Mimi Sheraton's one-star review of Nippon, 145 East 62d Street--ed.)