Worked it out! Since WP version 3.1 the hook for adding columns to custom post types has changed.
Before 3.1 it was:
add_action("manage_posts_custom_column", "testimonials_custom_columns");
After 3.1 you have to use this:
add_action("manage_testimonials_posts_custom_column", "testimonials_custom_columns");
So you have to specify the custom post type name in the manage_post_custom_column hook.
Hopefully this answer will save someone some time.