These are all good comments.  And I agree that the naming of the functions is not good (and the CamelCase).

Overall, yes, it should be made consistent and the types returned and passed in should be appropriate.  I did a little experimenting, using more imaplib functions in Python3, and I found the following...

In the case of Internaldate2tuple(), I use it as follows (and I suspect most would do the same):

    typ, data = src_box.fetch(src_msg, '(INTERNALDATE)')
    ...check typ here for error...
    src_internal_date = data[0]
    src_date_tuple = myInternaldate2tuple(src_internal_date)

So data[0] is a bytes array, returned by the fetch() method, and it is indeed therefore compatible with Internaldate2tuple().

In fact, it seems that the data, in general, is returned as bytes arrays in imaplib.  Given that we are dealing with raw email headers and bodies, this is perhaps exactly what should be done.  There is some grey area here.  For example, for headers, RFC 2047 discusses using special 'encoded-words' that are regular ASCII in, e.g., subjects (but I've encountered a few cases of UTF-8 in headers, even though this is a dubious practice).  IMAP flags are ASCII as well.

On the other hand, what you get from fetching pieces of emails are thing that you usually want to deal with as strings (e.g., you will want to do find() and startswith(), etc. on them).  But I guess it depends on what is really proper to use for email data.