Simmy,
first off, your site looks much better
I like the extra text on the homepage. Your links under 'services' look really good. You've made excellent use of pictures on each page too to detract from the text.
Add more content though. When I enter a page often only half of it is filled. Its true people dont like to scroll, but then they also like content so double it up in some areas, spamming your most important keywords where possible. Googlebot likes text. Think of it as pacman. It gobbles up text & keywords and looks sideways (to some degree) at pictures. Lots of text and a few pictures (with Alt-tags) to break it up makes for a happy robot

AND a pleasant browsing experience.
Is the link directory definitely worth while? They're asking me for $49 as my site has a PR of less than 3

When you say remove "bristol computer repair", do you mean the individual keywords?
The $49 is worth every cent in my opinion. I have over 600 links now and at least 300 of them would be from BRL at a guess. $49 for me is less than an hours work (or the equivalent of selling 2 antivirus licenses).
And yes, I would remove bristol, computer repair, pc, onsite & laptop, as they are already in your title or description meta-tags. (try removing them then run the SEO tool - you should still be at 100%). Removing these duplications will free up room to add some more words not already covered by your title/description meta-tags. Use the tool to find other common words on your site (one I see straight away is 'bristol onsite repairs'. Perhaps you could add this phrase as 'bristol onsite computer repairs', but make sure this term is found several times at least on your site (including the word 'computer').
Rather than keep the keywords that are left I would try using words such as - virus removal, spyware removal, mobile pc repair bristol, & pc networking bristol (also emphasis these services a bit more on your site). But make sure you check the result of adding these keywords with the SEO tool. If you need to, add these keywords/phrases a few more times on your site. It seems these are the main type of services you offer so spam them on your site & link them to keywords in your meta-tags.
Keywords such as - upgrades, computing problems, slow, blue screens, crashing, onsite, home callout are too general. Your never going to rank high for these keywords. You want hits for people searching for your services in Bristol so team this word up with your services. Its all about figuring out what keyword terms people in Bristol are using when searching for your services. Someone in India may search the keyword 'blue screen' but they may be looking to fix the problem themselves & their not going to come to you if they dont find a fix. It can be hard but it really is a case of understanding the psyche of potential customers in your area, and what keywords or search terms they use when looking for a local repairer. You could delete all of your remaining keywords & add some new ones emphasising specific services and still get a 100% result in SEO.
I've made a few changes to the directory structure of my website and as such, alot of the links on google are now out of date and don't link to anything. The site has been reindexed a couple of times since the changes were made but the old links still appear on google (they've been deleted from my web space). I've setup 301 redirects in htaccess for all of these pages - is this likely to affect my ranking at all? Will google eventually index my site properly so I can delete the redirects?
I really wouldnt worry about this. Google will sort out its caching over time. The main thing is your current links work. I notice your 'remote support' link is dead. This is something you need to fix (if your not working on it already). A current sitemap will help google update its links to reflect your current site.
I've made so many changes that i've dropped to page 2 again

Hopefully it will jump back up!
Again, I wouldnt worry. My site did the same after I made some changes. In my case, I removed a number of categories that I was linking to on BRL, as I read relevancy was important. Ive since put them back. If my PR goes back up it proves the number of links to my site is more important than relevancy.
This SEO business is actually really interesting and hopefully rewarding when you get it right
Yea I agree.
Edit: I also notice you have a heading 'Our services' on your homepage. Make this heading a hyperlink to
http://www.bristolcomputerrepair.co.uk/bristol-computer-repair/computer-repair.php - this will save a visitor having to scroll back to the top of the page & click 'services' (people are generally lazy when it comes to web browsing). You could also link the homepage heading 'Bristol PC repair service' to
http://www.bristolcomputerrepair.co.uk/bristol-computer-repair/onsite-pc-repair.php and on this page put your phone number and email address (at the top) or better still add another link on the 'onsite service & repair' page to your 'contact us' page.