I'm currently playing the 600 AD scenario as France, and for whatever reason, the Vikings aren't willing to trade their fur with me. I have a relations boost with them due to state religion (they're also Catholic), wisely chosen civic (I'm running Vassalage), and the +4 boost for giving them 10 gold when first meeting them. I do, however, have a -1 diplomatic penalty with them since I refused to join in their war against the HRE. Could this be why, when I hover over their furs in the trade screen, the red text displayed reads "We just don't like you enough"? It doesn't really make sense from a gameplay perspective for them to refuse to trade with me: I have surplus sources of wheat and wine, neither of which they currently have access to.
Also, I'm aware from my Mongol campaigns that you can have a state religion whilst running Animism, and I noticed that these Catholic Vikings were running the Animism civic. This strikes me as wrong somehow. You said the government and religion civic columns would be relatively unchanged in the upcoming civics redesign, but perhaps you can have Animism disable state religion in the same way that Pantheon does?