I have the exact same problem. A friend bought ME Trilogy while I had the standalone version. We get that same "Game Required" error regardless of how we try to invite eachother. We can both play on public servers just fine. The one difference here is that I can see my friend's Origin ID under the "friends who play" section...
I've tried reinstalling, repairing the installation on both computers... I'm wondering if due to the Trilogy naming that Origin thinks that they're two different games? And then it's still odd that we can both play on public servers, unless the Trilogy version is only connecting to other Trilogy players. Though your experience with finding eachother on public servers throws that theory into question.
Update: We can find eachother on public servers and play that way. I can start a server and my friend can join if he searches for a public match with the same settings as my lobby, but the error still shows up if he tries to join manually.