Here is a .pdf showing valid Bank of Japan banknotes. The 500yen and 1000yen notes you are describing are shown on page 2 and should have Iwakura Tomomi and Ito Hirobumi pictured on the face respectively. I don't know how much success you would have in exchanging these at a currency exchange in another country although you shouldn't have much problem in Japan.