I was enjoying a hearty bowl of Shrek cereal with my son this morning when my wife and I got to talking about movie-related cereals, and how there has been a boom in movie tie-ins (especially for kids) ever since Kenner and Hasbro started cranking out action figures back in the 70’s (thanks, Star Wars).
… and speaking of Star Wars, the earliest memories I have of a cereal deliberately created and marketed to tie in with a movie (as opposed to merely putting a movie character on a box of cereal already in production) are of C3PO’s. This was 1984.
Were there any others before that?
I’m sure someone could provide the definitive list from some online source -completely taking the fun out questions like these- but I can base my answer purely on recall.
Gremlins definitely had a spin-off cereal titled, well…. Gremlins I believe. The movie came out in 1984 so I don’t think it predates your C3PO’s but instead might point to when the cereal manufacturers started milking the idea.
Ralston brought out E.T. cereal in 1984, same year as Gremlins.
Do you want to count back in the 1930s when hot Ralston cereal sponsored the The Tom Mix adventures on the radio? There were loads of tie-ins between the two.
I seem to remember a smurf berry crunch in 1983…
I believe Murnau’s NosferatOs predated that by quite a few years. 
Indeed, in the stores by March of 1983.
In the early-to-middle 1950s, there was a Roy Rogers Cereal that was a tie-in with Roy’s television series. I begged and pleaded with my parents to buy some, but they wouldn’t give in, so I had to make do with Kellogg’s Corn Flakes.
The OP asked for a wholly new cereal based on a movie, not an existing cereal with a celebrity on the box.
For TV, Fruity Pebbles and Cocoa Pebbles (based around the Flintstones) were around at least back to the 70’s.
One of the cast of Saturday Night Live also got his own cereal during the 70’s: Frankenberry.
I have a box of those. It has American Idol’s Phil Stacey on the box.