It's not a blemish on your record that your new employer flaked out. That's a blemish on their record. Your job seems to like you, or they would have fired you for giving notice, right? So don't panic. Talk to your boss. It'll be an uncomfortable conversation, but that's par for the course in uncomfortable situations. You're still awesome.