Do five suffice? This is a hint
The problem becomes easier to deal with when you represent each country by a coloured dot and connect two dots by a line if the corresponding countries are neighbours. This gives you what is called a graph. An important property of this graph is that, because it comes from a map, no two lines in it cross each other.
Now look at the dots representing the new country's five neighbours and label them 1, 2, 3, 4, and 5 in cyclical order. What can stop you from recolouring dot 3 with the colour of dot 1? And what does that mean for the other dots?
If you are stumped by last issue's puzzle, here is the solution.
For some challenging mathematical puzzles, see the NRICH puzzles from this month or last month.