After a week of discussions with a local geocacher from Colombia I have decided to update the polygon data for the country. It's a major update.
Current region definitions will be thrown out. The current counties will be promoted to regions, which are a more proper match for what they really are. As counties there will be a mix of municipalities and "sub-regions", a bit depending on what exists and what's commonly used by the locals.
There are no challenge caches inside Colombia so I hope that this doesn't affect anything that needs to be updated.