I am trying to help a friend make a custom category menu appear like this:

About page:
Page Menu: Home | ABOUT | Services | Tips| Contact
Cat Menu: History | People | Non Profit |

Services page:
Page Menu: Home | About | SERVICES | Tips| Contact
Cat Menu: Repair | Sales | Consulting | Writing

Is it possible to have a custom Category Menu Based on the particular page you are on?

you would have to hard code the CAT menu twice. Then you could use CSS to only display the one you want on a particular page.

I'd put %cats in the header area and then look at the generated code and copy it (why rebuild the wheel). Then you can use this as the basis for your two hand crafted catmenu's. Make sure to give teh main <div> a unique ID for each like "about_cat" and "service_cat". Then you substitute your handcrafted menu for teh %cat.

Next in the CSS Inserts you could use

#about_cat {display:none;};
#service_cat {display:none;};
body.page-id-3 #about_cat {display:block !important;};
body.page-id-45 #service_cat {display:block !important;};

This assumes that the page ID for the about page is '3' and the ID for the service page is '45'. This will only display the category menu on those two pages.