You may need to use the full name for the Kernel here, it looks like gcutil is looking for the Google kernel in your private project:
'projects/hlabsgce/global/kernels/gce-v20130515'
instead of
'projects/google/global/kernels/gce-v20130515'
Try:
gcutil addinstance --image=hareem --kernel=projects/google/global/kernels/gce-v20130515 mynewinstance --project=my-project
gcutil should use the prefered kernel by default though, so you might not even need to supply that parameter.