Nelly Furtado had a hit with ‘I’m Like A Bird’ in her folky-pop style, but it wasn’t until six years later she had a huge album and hit single after hit single with the album Loose, which was produced by Timbaland and was mostly urban-pop.
British duo Everything But The Girl had middling-success with acoustic songs but got their big break with the full-on dance hit ‘Missing’, which then dictated a complete shift into house music for their remaining, popular albums.
Alanis Morissette was an unknown outside of Canada (and only mildly successful in Canada as a teen-pop singer) before she released Jagged Little Pill a did a genre switch to become… whatever genre you would call Alanis Morissette.
Tori Amos’ early projects like Y Kant Tori Read were more rock-oriented and were a complete disaster, her breakthrough came with the understated, confessional Little Earthquakes.
Janet Jackson made two albums of boring, bland teen-pop which put her on par with sister La Toya before she released the Prince-influenced, hard-hitting R&B album Control, which made her the second most successful Jackson.
Madonna started out in a rock band called The Breakfast Club before switching to club music.
Katy Perry used to be known as Katy Hudson and released one unsuccessful album of Christian pop.
Concerning critical success, Kelly Osbourne switched from watered down punk-pop to stylish electro and gained quite a few new fans with her second album Sleeping In The Nothing - it didn’t, however, translate to sales. (The album is good though - I swear)
Australian band Rogue Traders were a mostly unsuccessful dance act until they recruited singer Natalie Bassingthwaite and became a dance-rock group.
Some of those are arguable but I think all made a significant change in their genre/style and then became much more popular because of it.