Odin and Uncut is tricky since Odin himself spawns in 1 of 3 zones, I think. The only way you can tell he's up is if you see a unique weather icon on the mini-map and, depending on where you are, you may see little sparkly effects floating around you. As a rough estimate of his spawns, in East Shroud he'll be in the level 40s+ area. In Central Shroud he'll be around where the OP malboros are. In South Shroud, I think it'd be around the boars/keds, but I never saw him there myself.
I've also yet to see behemoth, but according to a friend of mine, he's a part of a FATE chain that would initiate in the SW end of Coerthas just south of Behemoth's Dominion, and eventually it'll lead up to there. I'm guessing the achievement would only come from the last FATE in the chain.
Violence good. Sexy bad. Yay America.