I can't think of anything that would cause the problems that you're describing. Are you absolutely sure that you're using the client ID of your app?

I've setup this small example and tested it with the client ID of four different apps, and it works like a charm:

@using Skybrud.Social.Instagram
@using Skybrud.Social.Instagram.Responses
@inherits System.Web.Mvc.WebViewPage

@{

    InstagramService service = InstagramService.CreateFromClientId("put your client id here");

    InstagramRecentMediaResponse response1 = service.Tags.GetRecentMedia("umbraco");
    <p>@response1.Body.Data.Length</p>

    InstagramTagResponse response2 = service.Tags.GetTagInfo("umbraco");
    <p>@response2.Body.Data.MediaCount</p>

}