I think it is helpful here to look at how the phrase "high places" is used. The Hebrew word is "bamah". This look will be chronological.
1) Samuel sacrifices at the high places, and many of his contemporary prophets are associated with these high places (1Sam 9, 10:5, 10:13). This is not contrary to Israelite religion, as Jerusalem had not yet been established as the place God chose to "dwell" (e.g. Deut 12:11, 17-18).
2) Solomon offered a sacrifice on a high place (1Ki 3:4)
3) Jeroboam (of Israel) built and offered on high places (1Ki 12:32, 13:2, 32), which remained even after the Assyrian invasion (2Ki 17:29, 32), and were finally destroyed by Josiah (2Ki 23:19-20).
4) Asa removed the high places of the foreign gods, and the high places in cities in Judah (2 Chr 14:3, 5), but did not remove all the high places in Israel (1Ki 15:14, 2Chr 15:17). His son Jehoshaphat removed the remaining high places from Judah (perhaps those who had been built since his father removed them, or those which were outside of cities). Yet at the end of his reign "the high places were not taken away" (2Chr 20:31-33) - a sin blamed on the people, not the king.
5) 1Ki 22:44 (I'll ignore this one, as it is textually dubious)
6) Joash (2Ki 12:3) and Amaziah (2Ki 14:4) and Azariah (2Ki 15:4) and Jotham (2Ki 15:35) did not remove the high places.
7) Hezekiah removed the high places (2Ki 18:4) together with the people (2Chr 31:1), but his son Manasseh rebuilt them (2Ki 21:3, 2Chr 33:3)
8) Josiah defiled the high places and destroyed some of them (2Ki 23:8-15, 2Chr 34:3)
In 2 Chr 14:3, Asa cut down the wooden idols in Judah, but according to 2 Chr 15:6 his son Jehoshaphat removed the wooden images from Judah. If one thinks about it, this isn't surprising. It is hardly a contradiction to say that my dad removed all the weeds from the garden, but that my mom removed all the weeds from the garden a month later. That is the nature of weeds and wooden idols: they spring up incessantly. It should not surprise us that this is the case for high places and altars: they are easy to build, and are sown by the festering idolatry in Israel - though at times this idolatry would have been suppressed and less visible.
In conclusion I suggest the following answer to your question: At the beginning of his reign, Jehoshaphat removed the high places in Judah associated with idolatry (that is, the high places on which they worshiped idols), and those in cities, and may have removed others also. Yet, as the hearts of the people were not with him, he probably failed to remove the rest, and new ones would have been built during his reign. As such, it says at the beginning of his reign that he removed most of them, but at the end of his reign that he had failed to move them.