I believe it was a preorder bonus. The set was either bought or arrived while I was at school, and I returned to find the movie and bonus material in a small cardboard box, so I imagine it was preordered through Toymaster or TRU or they were a lego catalogue exclusive. I do remember that they didn't add to the price, though. I thought it was the standard edition. I was only ten, though. Details are fuzzy.
...Though if you were talking about the Vakama, it wasn't packaged like the '01 version. It came in a single bag with movie images of Vakama on it, and I think the reverse side of the instructions was a movie poster.