Remove use of ''.format, as it is not well-supported in 2.6

In #1408 there was some discrepancy in the behavior of `str.format` between python 2.6 and 2.7.  Most uses of it are in error-handling and other lightly tested code, so let's just get rid of it.