Converting 4.5.x themes to 4.6.x
Search form
If your theme implements a search form, it needs to be altered. The search box <input> tag should have the name attribute set to edit[keys] rather than keys.
Node links
Node links no longer use the link_node() function, but instead are passed as an array in $node->links. PHP-based themes will need to be updated to pass this array through theme('links'). Template-based themes shouldn't need any changes.
Pages
The function theme_page() no longer takes $title or $breadcrumb arguments. Remove the two arguments and any special handling of them. All page titles and breadcrumbs are now retieved using drupal_get_title() and drupal_get_breadcrumb().
Node and comment markers
Node and comment markers are not restricted anymore to signal that something is new or that a form element is required. The required form element marker was moved to theme_form_element(), while theme_mark() was kept to generate content markers. New constants help in deciding on the marker to display: MARK_NEW signals new content, MARK_UPDATED is for changed or extended content and MARK_READ is for read or too old content. Now it is possible to output markers for read content too, and distinguish between new and updated content.
Pager and menu item themeing
Parts of the pager are now themeable themselfs. The menu theming was also reorganized, to be easier to add wrappers and theme menu links. If you override any of the theme_menu...() functions in your theme or template, compare them to the current versions in theme.inc and menu.inc to update them.
Text validation changes
Due to some changes in plain-text processing, some parameters which were HTML are now plain-text and vice-versa. If you use a theme engine, you shouldn't need any changes, except if you override extra theme_ functions yourself.
If you are seeing problems, the best approach is to compare every theme_ functions that you override with the one from Drupal core. In particular, the menu theme functions (theme_menu_*) require changes in the way l() is used.
You should also try submitting a node and a comment with HTML tags in the subject. The tags should come out escaped, and should be shown on screen rather than interpreted. If this is not the case, you need to check your theme_node() and theme_comment() functions.
Finally, page titles should be run through strip_tags() when put into the html <title> tag in <head>. This should only be a problem if you have a .theme theme, as the theme engines have all be updated to accomodate this change.