In this case I think that your best approach could be:
Fully analyzing your transaction and detecting which codes/ workflows / triggers... in general, the full apex transaction that is
affecting this Call.
To can track the and set the time of your Call Out to have an idea of what is happening and in combination with the developer console you
can detect when you are reaching this limit and based on that act
accordingly.
I will suggest to take a look to this link.
There is relevant information that will help you to investigated in which moment yo uare reaching this limit.
You can look the Apex Limit Class to help you with several limits to in your transaction:
getCpuTime()
Returns the CPU time (in milliseconds) accumulated on the Salesforce
servers in the current transaction.
getLimitCpuTime()
Returns the time limit (in milliseconds) of CPU usage in the current
transaction.
So you probably need to look your code as a full transaction for that Call out. What is firing, what is the full range of that operation. After having that clear you can start detecting why the call is timing out. It could be a SOQL, it could be that you are firing to many future calls or anything else that is costing and using execution time. Use the Limit Class to detect your limits.
I think in this situation with many components involve in a transaction you need to examine everything in order for you to get to the bottom of the problem. Run always the developer console behind to get log information. You could also deactivate some of the components that are part of your full transaction to see if perhaps they are the one causing this problem. Workflows, Triggers, or other components can be switch off to help you detect the main reason of why you are reaching this limit. Run the Call out clean of dependencies and check if you get what you expect. Start activating other components until to see which one is affecting the call out...this is probably the best way.
Run this call out in a separated sandbox, clean one with no other code. If the call out works fine there then you know start doing what I mentioned above, deactivation and activation of others parts of that transaction.
Good luck!