I sent off for some sample prints from Konika-Minolta on one of their A3 colour lasers a while back. Wasn't too impressed to be honest. Maybe it was their settings, but they lacked the vibrance i get from my canon i9950 inkjet. Pictures were printed on normal bog-standard 80gsm uncoated paper.
I personally wouldnt bother trying to print photos on a laser. If you're heart's really set on it though, go with AdWright, and get some decent heavyweight paper.