Did some more looking around...
For some reason, on my config, the functions in Sieve.php seem to return values that suggest my server supports DIGEST-MD5 when in fact it doesn't.
You can workaround the issue by removing the DIGEST-MD5 as a supported type in class Net_Sieve, but this seems to be a bit of a brute force mechanism to solve what should be a simpler problem. I'm fresh out of ideas on why this happening, any suggestions?