The task of labeling movies according to their corresponding genre is a challenging classification problem, having in mind that genre is an immaterial feature that cannot be directly pinpointed in any of the movie frames. Hence, off-the-shelf image classification approaches are not capable of handling this task in a straightforward fashion. Moreover, movies may belong to multiple genres at the same time, making movie genre assignment a typical multi-label classification problem, which is per se much more challenging than standard single-label classification. In this paper, we propose a novel deep neural architecture based on convolutional neural networks (ConvNets) for performing multi-label movie-trailer genre classification. It encapsulates an ultra-deep ConvNet with residual connections, and it makes use of a special convolutional layer to extract temporal information from image-based features prior to performing the mapping of movie trailers to genres. We compare the proposed approach with the current state-of-the-art methods for movie classification that employ well-known image descriptors and other low-level handcrafted features. Results show that our method substantially outperforms the state-of-the-art for this task, improving classification performance for all movie genres.