If a game doesn't work with the GBC Bios on, it doesn't work on a real gameboy. If it's just that game that doesn't work, I'd think that you have a bad rom. You can confirm this by trying it with the bios in another emulator - say, bgb. Or just try to find another rom.
This may seem random, but I was bored, so GameYob now supports GBS playback. Someone requested that months ago.
Though doesn't the GBC bios verify the ROM checksum (just like the Genesis/Megadrive) which will prevent most romhacks and homebrew roms (like Ultima 3) from working correctly unless you manually "fix" the checksum?