You can wait for 3 days and see if the game dismisses your previous pet. However, the game may have messed up and may continue to think that you still have an animal follower with you (or it may be stuck somewhere). This is the case for the stray dog will wait indefinitely if you command it to and cannot follow you again after 3 days.
To solve this, open the console and type:
set playeranimalcount to 0
*Kudos to Dyflinn432 for posting this fix here
UPDATE: If you don't have access to the Skyrim console, you can try the following trick which utilizes this bug:
Occasionally after killing the chief, rieklings still won't be
available as followers. Despite the rieklings not taking up the
humanoid follower slot, this bug may be circumvented by dismissing
your humanoid follower and recruiting them again after recruiting the
- Recruit a Riekling (if you are unable to, dismiss your follower and try again.
- Dismiss your follower and your Riekling
- Go to Markath, and buy a dog from Banning
- Dismiss the dog
- Recruit the Husky
Note that it will probably work if you skip steps (3) and (4). I included them because the original fix creator, Novoc at Gamefaqs, posted them.