Go with Rackspace. They're expensive compared to budget hosts, but they seem to have an army of sysadmins available 24/7/365 that never say "that's your problem" / "not in scope".
PS: that redirect bug is probably a mismatch of your site_url setting in either wp_blogs, the wp_options table of your primary blog, or the wp-config.php. If the domain set in any of those 3 places doesn't match you get that endless redirect loop. Could also be htaccess sending you to www or no-www, and your config is set the other way. Its an annoyingly common issue when moving MU sites, and they should have been able to fix it.