perl Makefile.PL CC=mpicc CCFLAGS="-lopenmpi -m64 -L/usr/local/lib/ope
+nmpi -L/usr/local/lib/" LIB=/usr/local/lib

...

gcc  -shared -O2 -g -pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -fexceptions -
+fstack-protector --param=ssp-b
+uffer-size=4 -m64 -mtune=generic Simple.o  -o blib/arch/auto/Parallel
+/MPI/Simple/Simple.so     \
             \
...

- libmpi.so defines the symbol openmpi_mpi_char:
...

-  However the file Simple.so does not appear to look for this lib:
...
[download]

The problem is that the Simple.so hadn't been linked against libmpi.so, because there was no -lmpi on the above link command line.

My guess would be that, first, you shouldn't say -lopenmpi, but rather -lmpi (as the lib apparently isn't named libopenmpi.so), and second, this argument shouldn't be in CCFLAGS, but rather in LIBS or LDDLFLAGS, because CCFLAGS is for the compile step, where -lmpi is irrelevant.  (The annoying thing with LDDLFLAGS is that it replaces the defaults (instead of adding to them), so you'd have to manually add whatever perl -V:lddlflags reports.)

In case that doesn't help, you could simply re-issue the link command manually with the -lmpi appended (plus -L... etc.), rather than trying to convince MakeMaker to automatically issue the commands you want.  I.e. something like

$ gcc  -shared -O2 -g -pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -fexceptions
+ -fstack-protector --param=ssp-buffer-size=4 -m64 -mtune=generic Simp
+le.o  -o blib/arch/auto/Parallel/MPI/Simple/Simple.so  -L/usr/local/l
+ib/openmpi -lmpi
[download]