$links in hook_link_alter() an object???

The line you point to is in hook_link_alter() in which $links is an array:
http://api.drupal.org/api/function/hook_link_alter

Changing the line as you suggest would break the module.

I don't know anything about contemplate. Maybe its maintainer can explain why $links has turned into an object...

I recognize that this issue is old, but I'm seeing the same behavior with Outline 6.x-00-alpha2 (despite the name, an official release for 6.x) and contemplate 6.x-1.0. I've outlined the problem below, and my major question is: does Outline need the bugfix, or does Contemplate? The maintainer for Outline is pointing to this thread, so I'd like to find out once and for all whose queue this bug needs to be in.

With the outline module enabled, attempting to create new OR edit existing content templates at admin/content/templates/[content-type] provides the following error:

Fatal error: Cannot use object of type stdClass as array in /var/www/sites/all/modules/outline/outline.module on line 196

Here's the function in question from outline.module:

<?php
function outline_link_alter(&$links, $node) {
  // Since hook_link_alter is called several times, it's easier to unset the book_add_child link
  // which has already been replaced by our own in outline_link().
  if (isset($links['book_add_child'])) {
    unset($links['book_add_child']);
  }
}?>

The line if (isset($links['book_add_child'])) { is the line producing the error. The API page for hook_link_alter does say that $links should be an array, and the maintainer of Outline module says in #287561: $links in hook_link_alter() an object??? that changing that line breaks the module.

While this is broken I can either 1) have the Outline module or 2) be able to edit content templates, both of which my site needs.

Is this an issue with Contemplate or Outline?

The problem is definitely with contemplate module for the reasons explained by you and myself. Check with the contemplate module maintainer, and/or patch contemplate.

The fault is in Contemplate module. It passes argument to hook_link_alter() in an incorrect order.

Changing
$function($node, $node->links); to
$function($node->links, $node);

in contemplate_node_view() function will fix the problem.

if you would like to provide a patch I would be happy to look at it