Pumpkin seeds have been a lifesaver when I just can't stop that snacky feeling. I also love good chicharones/pork cracklins, which is fried pig skin often times with some fat still on it. I'm not sure if it's primal, but it seems like it should be.
P.S. "Pork cracklins" seems like the most redneck American snack I could think of, I'm not sure if those are available in the UK, but try not to knock them till you try them.