I remember the video quite clearly. There was a 'male' milk carton that went on an adventure and fell in love with a 'female' milk carton. It was a really original concept.
The artist is 'Blur' and the name of the song is 'Coffee & TV'. It is on their album entitled '13'.