I'm doing some data transmission from a dsPIC to a PC and I'm doing an 8-bit CRC to every block of 512 bytes to make sure there are no errors. With my CRC code enabled I get about 33KB/s, without it I get 67KB/s. 

What are some alternative error detection algorithms to check out that would be faster?

While there may be faster options than CRC, such as Fletcher, if you use them then you are likely to end up sacrificing some degree of error detection capability. Depending on what your performance and error detection requirements are, an alternative may be to use CRC code optimised to your application instead.
For a comparison of CRC with other options, see the excellent answer by
Martin Thompson.
One option to help with this is pycrc which is a tool (written in python1) which can generate C source code for dozens of combinations of crc model and algorithm. This allows you to optimise speed and size for your own application by selecting and benchmarking different combinations. 1: Requires Python 2.6 or later.
It supports the crc-8 model, but also supports crc-5, crc-16 and crc-32 amongst others. As for algorithms, it supports bit-by-bit, bit-by-bit-fast and table-driven.
For example (downloading the archive):
$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

You can even do funky things like specify using dual nibble lookups (with a 16 byte look-up table) rather than single byte look-up, with 256 byte look-up table.
For example (cloning the git repository):
$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Given your memory and speed constraints, this option may well be the best compromise between speed and code size. The only way to be sure would be to benchmark it though.

The pycrc git repository is on github, as is its issue tracker, but it can also be downloaded from sourceforge.
