Well, it looks like that networking restart line is necessary on my hosting environment as well, so my work-around is to add the ifdown/ifup commands to /etc/rc.local, after the networking restart. This works for me, but of course, does not get us any closer to the root of the problem with the network interfaces failing to come up in the first place.
Here's my modified version of /etc/rc.local:
#!/bin/sh -e
#
# rc.local
#
# This script is executed at the end of each multiuser runlevel.
# Make sure that the script will "exit 0" on success or any other
# value on error.
#
# In order to enable or disable this script just change the execution
# bits.
#
# By default this script does nothing.
/etc/init.d/networking restart
/sbin/ifdown lo
/sbin/ifup lo
exit 0
Hope that helps someone!