The guess may have felt stupid, but it was correct
I would also add to look at the screens in the "Intelligence" tab; just under the "Observation priority" line is a line for "Espionage budget" that has two numbers separated by a slash; the first is how much you are spending on the currently selected country with your currently selected espionage budget and country priority, that after the slash is the "par" upkeek costs of the spy network you currently have in that country. If the first number is lower than the second your network will tend to shrink and/or be ineffective; if the first number is higher then your network should tend to grow/succeed slightly more often.
Note that the priorities work on a pro-rata system, so increasing one country's priority will effectively reduce that of all others a little. To increase spending in one area you will need to both increase its priority and increase the overall budget.