There is another shop downtown, Lewis Pipe and Tobacco. It's on 6th and Marquette. I'm not sure what their hours are, they may not be open during on the weekend, and I'm sure they are closed by 6. The selection is 'ok'. The owner is a very good guy. Otherwise, the shops Joe listed are your best option. Tobacco Grove is a fantastic cigar shop. Great selection, and great smoking lounge. Looks like a shipment of Opus just came around as well. The only two shops that would have those are Tobacco Grove and Stogies on Grand (St. Paul).
Have fun.