I believe there is a way to do it so that the MD5 collision would only be 2^64. This is also how MD5 collisions can be created without any special techniques, meaning that MD5 was always only barely more secure than 56-bit DES for example.

Once they have a collision in the sha1 portion, making changes so the md5 portion also collides should only take a few CPU seconds.