If you are talking about the new V2, I believe it is only available directly from the developer. Link below.
http://www.alfredapp.com
Does this mean even when I initially bought this app from the AppStore I have to download a new one from this given site?
Ok thanks guys
https://buy.alfredapp.com/upgrade
Punch in your V1 license info here and it will show you your upgrade options. V2 is nice upgrade and well worth the $$ IMO.
Will I be able to use my apple redeemed credit to buy this?
Hmm... dunno. If you look in the Powerpack pane of Alfred prefs do you see a reg. code?