Think like apache - wherever link points to, the user apache runs on ( or probably the one assigned for virtualhost if you use FastCGI) has to have filesystem access to this destination. You can "fix" it in a few ways:
1) like you described, chmodding directories
2) you add add user to the same group as apache and make directories group readable
3) instead of chmodding it for apache you can do opposite direction - link it for the user, and put in physically under apache's htdocs tree ( or add apache user to some group user belongs to, and make his directory group readable )
4) you can use "mount -bind" to mount destination into some directory visible by apache. There's a way to use suexec to do it dynamically, however if it's specific case and one directory, you could just mount it by hand I guess ( possibly put mount -bind into fstab if needed )
Anyway, like arkascha said, it's permission problem, mostly solved by manipulating group ownership/group readable right.
Oh, and when you need to CHECK if it works, I mean if apache sees what it's supposed to see, you can make sure it does with sudo-ing to apache user ( from the root session, like "su -s /bin/bash www-data" ) - and while being apache user, try simply "cd" to that directory. So if this user will be able to go to specific directory, webserver which works as "him" will be able too.
6) Theoretically, you could also configure apache to run as the same user you need to access directory to (instead of www-data or so), but this will probably be the worst idea of them all :)