I think you have got the directions wrong. You were probably looking in an easterly direction. You would have seen Venus about 45 degrees and up a bit as you say. There's a nice tool called Stellarium which you can download to see what the sky might have looked like at different times. If you'd been looking westerly you might have seeen Mars - which is what I thought you meant at first, but it was not in the same region of the sky as the moon.
http://stellarium.org/en_GB/