SEO Not Working in My WordPress Theme

You need to discuss this with your current theme developer.

Maybe you need to consider hiring another developer? It’s likely that the whole theme might need to be examined.

I was actually able to fix the keywords and descriptions by adding this piece of coding to the header.php file: <?php wp_head(); ?>

In that case, make sure that footer.php also contains <?php wp_footer(); ?> – preferably right at the end of your displayed footer. Some plugins use this as a hook too.

still having problems with getting the titles to show up

Is this the meta-title?I If so, try dropping a copy of your theme’s header.php file into the WordPress pastebin and post the pastebin url here. Perhaps someone will be able to spot the problem and suggest a solution.

Same happens when I deactivate the theme and try and use the base WordPress theme — Plugin issue?

That could well be the case. HeadSpace2 can cause problems in WP 3.0:
http://wordpress.org/support/topic/411432

Try replacing:

<title><?php if (is_home () ) { bloginfo('name'); }
elseif ( is_category() ) { single_cat_title(); echo ' - ' ; bloginfo('name'); }
elseif (is_single() ) { single_post_title();}
elseif (is_page() ) { single_post_title();}
else { wp_title('',true); } ?></title>

with:

<title><?php if (is_home () || is_front_page() ) { bloginfo('name'); }
elseif ( is_category() || is)tag() ) { wp_title(' - ',true,'right'); bloginfo('name'); }
else { wp_title('',true); } ?></title>

Sorry – typo! Try:

<title><?php if (is_home () || is_front_page() ) { bloginfo('name'); }
elseif ( is_category() || is_tag() ) { wp_title(' - ',true,'right'); bloginfo('name'); }
else { wp_title('',true); } ?></title>