I am currently running my blog, which is a photography blog with 5G bandwidth used per day on a dedicated server Pentium 4 CPU 2.80GHz, 1024 KB RAM server. I got around 4000 uniques per day traffic and the site is getting larger and larger. Just these two weeks I have been experience downtime and slow loading for the site.

The WHM tells me that my server load is constantly at 2.5 smth and is in red. I contacted my host but everytime they just said the server load at the time they checked was less than 1.

What should I do? Is my dedicated server not good enough to hold the blog? I mean, I have seen people with 10000+ or even 20000+ uniques/day sites running perfectly fine on a dedicated server. Why mine has such problem?

I'd go for another 1GB of ram, I expect you meant 1024 MB RAM of ram?
The extra memory will make a huge difference and optimize your server

Extra RAM should help, even though I feel your current setup is more than enough for 4000 uniques.

Ram will help but it seems that your current server should meet your requirements just fine.

Does the blog have alot of photos? I noticed it was a photo blog.

Why don't you get a server load monitor such as the munin service monitor and look at the average server load after a day...?