Quite the problem is mis-matched time on the Learn server and the tool provider. So first, make certain both servers are running some means of syncing to a time server, ex: ntpd. Second, from a case that I needed help from our OAuth expert with, make certain that the code that calculates the OAuth signature includes everything, including the port. Example: If the Learn server is available on https://mybig.co.com:8443 then the OAuth signature calculation for the LTI launch must include the 8443 portion of the URL.
May all your LTI launches be successful!