I'm almost positive the collection was called "Eshu".
If I remember correctly, the whole story of the collection was this idea of a woman from Victorian era Europe traveling to Africa, and slowly the African culture blends with her own until it completely takes over....something to that effect. You can definitely see inspiration from the 1840s/50s in the leg-o-mutton sleeves, hoop skirts and corsets, and of course the inspiration from some of the darker, more mysterious things about various African cultures.
Here's a review from nytimes.com.
This collection is actually my first memory of McQueen, the first collection of his I remember seeing. I'd say it was a pretty accurate first impression; the aggressive and barbaric mixed with the romantic and feminine. That's kind of McQueen in a nutshell.