ghostscript command does not work on my hardy system

I was trying to run gs command on the ubuntu8 system to convert a Japanese PDF. The command i was using is:
gs -dSAFER -dBATCH -dNOPAUSE -dQUIET -dFirstPage=1 -dLastPage=1 -sDEVICE=jpeg -sOutputFile=a.jpg a.pdf
and I am getting following error

Error: /undefinedresource in findresource
Operand stack:
   --nostringval-- --dict:8/17(L)-- 2 MSPGothic 8 --dict:5/5(L)-- --dict:5/5(L)-- MSPGothic --dict:10/12(ro)(G)-- --nostringval-- --dict:7/7(L)-- --dict:7/7(L)-- Adobe-Japan1 CIDFont Adobe-Japan1
Execution stack:
   %interp_exit .runexec2 --nostringval-- --nostringval-- --nostringval-- 2 %stopped_push --nostringval-- --nostringval-- --nostringval-- false 1 %stopped_push 1905 1 3 %oparray_pop 1904 1 3 %oparray_pop 1888 1 3 %oparray_pop --nostringval-- --nostringval-- 5 1 4 --nostringval-- %for_pos_int_continue --nostringval-- --nostringval-- --nostringval-- --nostringval-- %array_continue --nostringval-- false 1 %stopped_push --nostringval-- %loop_continue --nostringval-- 409583 --nostringval-- 1853 4 11 %oparray_pop --nostringval-- false 1 %stopped_push 1852 4 11 %oparray_pop --nostringval-- (gstatetype) --dict:0/0(L)-- --nostringval-- false 1 %stopped_push --nostringval-- %loop_continue --nostringval-- --nostringval-- --nostringval-- --nostringval-- --nostringval-- --nostringval-- %array_continue --nostringval-- --nostringval-- --nostringval-- --nostringval-- --nostringval-- %loop_continue --nostringval-- 1856 14 11 %oparray_pop findresource %errorexec_pop --nostringval-- --nostringval-- --nostringval--
Dictionary stack:
   --dict:1155/1684(ro)(G)-- --dict:2/20(G)-- --dict:97/200(L)-- --dict:97/200(L)-- --dict:107/127(ro)(G)-- --dict:275/300(ro)(G)-- --dict:22/25(L)-- --dict:4/6(L)-- --dict:25/40(L)-- --dict:5/5(L)-- --dict:16/20(L)-- --dict:38/40(ro)(G)--
Current allocation mode is local
Last OS error: 2
GPL Ghostscript 8.61: Unrecoverable error, exit code 1

I have did some research on this particular error. And everything leads me to the conclusion that I have some CMAP that is missing. I think i have install all the cmap debians I could find (cmap-acrobat-japan1, cmap-acrobat-japan2, cmap-acrobat-bg, cmap-acrobat-korean, cmap-acrobat-cns). could someone give me a clue of what exactly this error means and what may i do to fix this??
Thanks so much.