How do I get the UTC time of "midnight" for a given timezone?

I think you can shave off a few method calls if you do it like this:

>>> from datetime import datetime
>>> datetime.now(pytz.timezone("Australia/Melbourne")) \
            .replace(hour=0, minute=0, second=0, microsecond=0) \
            .astimezone(pytz.utc)

BUT… there is a bigger problem than aesthetics in your code: it will give the wrong result on the day of the switch to or from Daylight Saving Time.

The reason for this is that neither the datetime constructors nor replace() take DST changes into account.

For example:

>>> now = datetime(2012, 4, 1, 5, 0, 0, 0, tzinfo=pytz.timezone("Australia/Melbourne"))
>>> print now
2012-04-01 05:00:00+10:00
>>> print now.replace(hour=0)
2012-04-01 00:00:00+10:00 # wrong! midnight was at 2012-04-01 00:00:00+11:00
>>> print datetime(2012, 3, 1, 0, 0, 0, 0, tzinfo=tz)
2012-03-01 00:00:00+10:00 # wrong again!

However, the documentation for tz.localize() states:

This method should be used to construct localtimes, rather than passing a tzinfo argument to a datetime constructor.

Thus, your problem is solved like so:

>>> import pytz
>>> from datetime import datetime, date, time

>>> tz = pytz.timezone("Australia/Melbourne")
>>> the_date = date(2012, 4, 1) # use date.today() here

>>> midnight_without_tzinfo = datetime.combine(the_date, time())
>>> print midnight_without_tzinfo
2012-04-01 00:00:00

>>> midnight_with_tzinfo = tz.localize(midnight_without_tzinfo)
>>> print midnight_with_tzinfo
2012-04-01 00:00:00+11:00

>>> print midnight_with_tzinfo.astimezone(pytz.utc)
2012-03-31 13:00:00+00:00

No guarantees for dates before 1582, though.

@hop's answer is wrong on the day of transition from Daylight Saving Time (DST) e.g., Apr 1, 2012. To fix it tz.localize() could be used:

tz = pytz.timezone("Australia/Melbourne")
today = datetime.now(tz).date()
midnight = tz.localize(datetime.combine(today, time(0, 0)), is_dst=None)
utc_dt = midnight.astimezone(pytz.utc)        

The same with comments:

#!/usr/bin/env python
from datetime import datetime, time
import pytz # pip instal pytz

tz = pytz.timezone("Australia/Melbourne") # choose timezone

# 1. get correct date for the midnight using given timezone.
today = datetime.now(tz).date()

# 2. get midnight in the correct timezone (taking into account DST)
#NOTE: tzinfo=None and tz.localize()
# assert that there is no dst transition at midnight (`is_dst=None`)
midnight = tz.localize(datetime.combine(today, time(0, 0)), is_dst=None)

# 3. convert to UTC (no need to call `utc.normalize()` due to UTC has no 
#    DST transitions)
fmt = '%Y-%m-%d %H:%M:%S %Z%z'
print midnight.astimezone(pytz.utc).strftime(fmt)