Both of my grandparents on my father's side were Romanian. Both Jewish. My grandmother was born in Bucharest, but there's some discussion about my grandfather (the most he'd say about his birth town is that "I'd go to sleep in one country and wake up in another"). I don't speak Romanian. They left Romania before my father was born. Though my grandfather came from a numerous family, we have no known living relatives on his side. I do have their marriage certificate, with their parent's names and the address where they lived in Bucharest in 1937 (of course, it doesn't exist anymore). The thing is: I do not know where to go from there. Two additional problems I have found: My grandmother's maiden name is VERY common, and my grandfather's surname was apparently shortened from it original form (by either his father or his grandfather), but there's no-one left to tell me what was the original surname. Any ideas as of how to proceed from here?
You didn't include which country your grandparents emigrated to or where your father was born. Later official records in the new country (naturalization, application for social security or equivalent) may include the place or the region of your grandfather's birth. Could there be keepsakes or letters from relatives somewhere in storage? These may provide old names and addresses and clues in the text to investigate further.
Your grandfather's statement about changing countries overnight points to the territorial changes at the end of World War I. Romania gained Transylvania and some other Hungarian regions in the Treaty of Trianon. It also acquired other territories in the north and east (see Greater Romania).
If you find a placename for your grandfather's birth, it probably will not be the current placename. It may be a historical version in one of the languages current in that region. It will take some investigation in gazetteers and comparison lists and the Stetlseeker databases to identify correctly.
There are groups working on indexing the various Jewish censuses and registrations in eastern Europe. You'll need to check current coverage of records and how to work with these (not my area of expertise). There may be regional differences in surname distribution that will help narrow down possible regions even with the surname change you mentioned.
For Jewish information on Romania, I recommend two sources of information to go to first:
The Avotaynu journal has been published quarterly for 25 years and has the best articles available on Jewish Research. Over that time, they've published 33 articles on Romania. The journal is not free, you might be able to find a local library that has back issues. Otherwise, I would recommend you purchase their CD of all previous issues for $100.
In addition, you should definitely check out JewishGen and what it has to offer. They have a FAQ that is great guide to the site, and to Jewish genealogy in general.
You will have to join JewishGen for some of its services, but registration is free.
Also be sure to check JewishGen's online resources (at the end of their FAQ), and even though your ancestors may have a very common surname or a shortened surname, the combination of the possible names and the city of Bucharest may connect you to some databases with information, or to other researchers to whom you may be related.