Have you checked your downloads? Sometimes that can be a big memory eater. Also, this is a good program to check space. Disk Inventory X After you run it, it is pretty much self explanitory. When it finishes its lookup on your hard drive, it will arrange your items into colors. There you can see what is killing the space. Little file sizes may not seem like a threat, but when you add it all up, it becomes a big space killer. You can also click the colors and it should open them in your finder.
Hope this helps.
To get a more accurate reading on your available HD space:
Then check again.
Follow the suggestions here as well: http://docs.info.apple.com/article.html?path=Mac/10.7/en/mchlp1235.html
Try using a storage allocation tool to see where the files are that are taking up the space:
Use caution when removing files. If you don't know what a file is, don't remove it. Make note of where that file is stored using one of the tools above and report back with the location.
SafeBoot and PRAM are fairly standard troubleshooting steps for a variety of issues. Feel free to read the articles and ask any questions you might have.
SafeBoot does run a repair of your drive (which is a good idea to do occasionally) and should not cause issues unless the drive is so severely damaged that SafeBoot cannot repair it and it pushes the drive over the edge (rare but I've seen it).
As long as you keep regular backups you should be fine: http://support.apple.com/kb/HT1427
If you don't keep regular backups, you should start ASAP. Everyone should backup their data (unless they don't care about it).
Glad the articles were helpful.