Guy, awesome, this narrows things down a bit. Can you also install these debug symbols and repeat the trace?:
I'm guessing that this is a bug in PHP or curl that isn't re-initializing some kind of global state for openssl.
Are you definitely using the curl module for php? If not, you can try
apt-get remove php5-curl
And see if that resolves the issue. Please report back if that does (as it will help us to isolate the issue).