I suppose it is my fault that I didn't check to make sure my host wasn't listed as a spammer, but is there any way I can get around this so that I can send email? When a host is on a block list, do they block the host's entire block of IPs so that if I were to get a dedicated IP I would still be blocked by people? Just wondering if I am completely screwed over by this (I guess I get what I pay for). Thanks for any help.

You will need to contact your Hoster and have them do what needs to be done, for removal off the Spam list(s). If they won't do it -- usually requires cancelling one or more Spammer's account which some won't do -- then your only option is to find another Hoster.