Porygon-Z - When I first saw it, my initial thought was "over-designed" and I much preferred the simplicity of Porygon2 or the retro Porygon. When I needed something for Trick Room that wasn't Psychic I decided to try it since it also learned the move naturally. I now love almost everything about it and can't wait to hear its updated cry in X/Y (it was already pretty good).
Gallade - I was a big Gardevoir fan back when RSE came out (NOT that way...) and was initially not willing to use Gallade since I much prefer special Psychic types. But I slowly realized that I needed something physical with really good coverage and Medicham wasn't going to cut it. Gallade was a very viable choice, but I didn't quite like its design. I now like it a lot more and, though not as much as Gardevoir, it's definitely in my Top 20.
Mandibuzz - I thought the idea of a vulture-based Pokemon was pretty bad and when I first saw its design I just confined it to the PC and never looked back. But looking at it several times over the past couple of years has actually softened my stance on it and I now think its design is ace and am considering using one competitively.
Muk - When I first saw Muk, I thought it was a pile of (literal) crap. Cue the anime presenting Ash's Muk and I suddenly chuckle whenever I see Muk or hear its cry. It wasn't until Gen 3 came around that I thought about using Muk though and I'm glad I did since it has such utility with that bulk and Attack.
Mantine - It looked goofy and wasn't a good Pokemon at all, so I never used it at all for the first 4 Gens. It has only been this Gen I've turned around and thought "You know, it really doesn't look THAT bad". I've yet to use Mantine, but that's only because I can't really make it fit on a team easily.